CN102394794A - Coordinated monitoring method for preventing BGP routing hijacking - Google Patents

Abstract

The invention relates to a collaborative monitoring method for preventing border gateway protocol (BGP) route hijacking (including prefix hijacking and next hop hijacking). The technical solution is: the AS participating in the collaboration uses the original or newly established server to run the BGP protocol, establishes a BGP session for collecting routing update messages with one or more internal routers, and communicates with monitoring servers in multiple other ASs at the same time. Establishing a cooperative monitoring session is specifically composed of two parts: a routing update monitoring method and a session state monitoring method. On the control plane, analyze the routing update messages obtained by the monitoring session, and detect BGP prefix hijacking and next-hop hijacking; on the data plane, maintain and detect the status of the collaborative monitoring session, and discover routing hijacking events aimed at the cooperative network itself in real time . The present invention makes full use of the existing network management and measurement facilities inside the AS, as well as the data collection facilities set up by the public routing data release project, and builds a monitoring system for BGP prefix hijacking and next-hop hijacking through collaboration and integration of existing network resources. collaborative network.

Description

Take precautions against the synergic monitoring method that the Border Gateway Protocol route is kidnapped

Technical field

The present invention proposes the synergic monitoring method that a kind of strick precaution Border Gateway Protocol (BGP) route is kidnapped (comprising prefix hijack and next jumping abduction), belongs to the computer network security technology field.

Background technology

The Internet is the product that the computer technology and the communication technology merge each other; Since the mid-90 in 20th century; Along with the quick growth of network size and increasing based on the commercial application of the Internet, the Internet just progressively develops into and is the important information infrastructure of human society.In order to strengthen extensibility, the Internet has adopted the routing architecture of hierarchy type, and (Autonomous System AS) is divided into " in the territory " and " between the territory " two levels on the granularity in autonomous system.Autonomous system is defined as and operates under the unified strategy, outwards shows one group of routing device of consistent routing policy.Border Gateway Protocol (BGP) is current inter-domain routing protocol de facto standards, and it mainly acts on is that switching network can reach information between autonomous system.Route system based on BGP is the core infrastructures of the Internet, makes and is distributed in the worldwide network terminal, equipment can communicate through the Internet.

It is the current the most serious security threat that faces of BGP route system that route is kidnapped, and specifically is divided into prefix hijack and jumps abduction with next.Prefix hijack directly translates into the IP address space (victim network) that an AS (assailant AS) has declared to belong to another one AS (victim AS).In the course of internet development, the prefix hijack incident happens occasionally, and has seriously disturbed the normal operation of the Internet, influences bigger AS 7007 incidents that comprise 1997, and Google in 2005 is by the Cogent kidnapping accident, and YouTube incident in 2008 etc.The service that these incidents have all caused victim network to provide was interrupted more than two hours.The excessive unconditional trust between the bgp neighbor that has its source in of BGP prefix hijack.Each AS carries out the selection of optimum route according to the route of acquiring from neighbours AS, uses optimum routing forwarding data then, and can in fact can not judge the credibility of route.When prefix is kidnapped generation, gather project by means of routes such as RouteViews and RIPE-RIS, can find from route data that victim's network simultaneously by two or more different AS declarations, possesses obvious characteristics.Another kind has more concealed attack pattern and is called next jumping abduction, and the false title of assailant AS oneself is the immediate neighbor of victim AS.Owing to have only victim AS itself just to know the whether neighbours of oneself of assailant AS; And prefix hijack/next is jumped and kidnaps when taking place; The wrong route that assailant AS sends generally can not propagate into victim AS itself, so prefix hijack is jumped all extremely difficult detection of abduction with next.

Kidnap in order to take precautions against route, academia and industrial quarters have been made a large amount of effort, and current work mainly concentrates on two aspects.The one, to fragile BGP trust model,,, be the method that limits " what only allows to do " in itself for BGP provides comprehensive protection through the design safety protocol; The 2nd, to prefix hijack,, be the method that limits " what permits no. " in itself through route and data forwarding paths to particular network are monitored the safety that guarantees prefix.Aspect the security protocol Mechanism Design, still do not form an acceptable scheme on effect and cost at present, its reason is many-sided.One of which, most security protocol mechanism all need be revised Routing Protocol, dispose of a high price; Its two, calculating on the router and storage resources are all very limited, and the realization of security protocol often needs bigger expense; Its three, a lot of security mechanisms all need PKIX (Public Key Infrastructure, support PKI), and this extremely difficult realization on distributed the Internet in the network-wide basis; Its four, say on the driven machine that the security mechanism of current proposition often only could be benefited after the network-wide basis deployed, the operator that commercial interest drives often lacks power and goes to dispose.Equally, be devoted to detect the monitoring mechanism of prefix hijack and also do not promoted widely, its reason comprises following three aspects.The one; Mapping meeting between network prefix and the proclaimers AS is along with commercial relations change; A current not authority's mechanism or data source can provide accurately real-time mapping relations, have only the owner of network prefix itself to know just whether the variation of mapping relations is legal; The 2nd, owing to be the relation of vying each other in essence between the operator, the AS that observes prefix hijack does not notify the obligation of victim AS, often lacks to handle timely and control; The 3rd, when prefix is kidnapped generation; The network communication of other AS to the Internet of being held as a hostage is cut off to a great extent; Therefore, commonly usedly between the network manager pass through the means that Email etc. depends on the Internet and lost efficacy basically already even have AS to be ready to notify AS to the victim with this prefix kidnapping accident.

The proposition of the inventive method is based on following brass tacks:

(1) importance of routing safety becomes increasingly conspicuous, and route is kidnapped to take precautions against have demand and vast market widely.Correlative study shows that the distribution of internet traffic between network prefix is unbalanced, and a few subnetwork prefix has been carried a large portion flow in the Internet.(the Internet Content Provider of content supplier of online services such as internet hunt, video sharing and real-time news is provided; ICP) service quality seriously depends on route system, and can the flow that be embodied in the service that provides with ICP and be the destination correctly be routed to this ICP provides the network of service.The direct embodiment that route is kidnapped is exactly " flow absorption ", thereby assailant AS can reach the purpose of redirect traffic to self through the route of kidnapping victim network, therefore takes precautions against route and kidnaps particularly important for ICP.

(2) abduction is taken precautions against and need be worked in coordination with to route.The strick precaution that the BGP route is kidnapped exists a pair of natural, implacable contradiction.On the one hand, have only the owner of network prefix itself could differentiate that whether the route variation is owing to attack causes; On the other hand; The wrong route that the mechanism of BGP propagation route and the routing policy of Virtual network operator make the assailant initiate is difficult to propagate into victim AS itself; Therefore; The route propagation mechanism that depends on bgp protocol itself can not let the route of AS protection oneself not be held as a hostage, and must introduce the collaborative wrong route that lets the assailant initiate and can propagate into victim AS.

(3) route data is gathered project RouteViews and RIPE-RIS, and the issue route data supplies network academic research and uses towards the route Monitoring Service of whole Internet, with more than 400 autonomous system that spreads all over the world with set up bgp session.These autonomous systems have been set up and have been aimed at RouteViews and RIPE-RIS provides the network infrastructure of data, but self do not obtain targetedly effectively Network Security Service.Simultaneously, most AS have oneself in the Internet network measure, handling facility are monitored routing state in the territory and flow distribution, and the network equipment is managed.The synergic monitoring method that this method proposed through these are idle at ordinary times or utilance is very low among the collaborative AS facility to the BGP route hijack attack monitor; AS need not carry out extra investment just can obtain extra repayment, helps the promotion and application of this method.

Summary of the invention

The technical problem that the present invention will solve is through making full use of existing network management and Fundamentals of Measurement facility in a plurality of autonomous systems (AS); Structure is used to monitor the contract network that Border Gateway Protocol (BGP) route is kidnapped, to strengthen the fail safe of the Internet inter-domain routing system.

Technical scheme is: participate in collaborative AS and utilize server operation bgp protocol original or that newly set up; Set up the bgp session that is used to gather route updating packet with one or more internal routers; While is set up the synergic monitoring session with the monitor server among a plurality of other AS, specifically is made up of routing update monitoring method and session status monitoring method two parts.At control plane, analyze the route updating packet of monitoring acquisition conversation, detect the BGP prefix hijack and kidnap with next jumping; At datum plane, the state of synergic monitoring session is safeguarded and detected, find to be directed to the route kidnapping accident of contract network itself in real time.

The term of redetermination of the present invention has monitor, monitoring session, monitoring neighbours, inner neighbours and external neighbor etc.Monitor is each monitor server that AS set up of participating in making up the synergic monitoring network; The bgp session of setting up between the monitor that is used to communicate by letter is referred to as to monitor session; Correspondingly, two monitors of a monitoring session connection are called the monitoring neighbours; Whether according to being in the same AS, the bgp neighbor relation of monitor and other routers or monitor server is divided into inner neighbours and external neighbor.

Other symbols that the present invention uses and term are explained as follows:

Network prefix: a continuous IP address block is expressed as a network prefix in route system, is called for short prefix;

M ₁, M ₂... M _n: set up n monitor of monitoring session with autonomous system u, among the present invention the description of all methods all from the angle of autonomous system u, the monitor that hereinafter will not distinguished autonomous system and set up;

I _m: the prefix sets that monitor m attempts to protect refers to the directly all-network of declaration of ASm in the present invention;

Ipe _m: monitor m is used for setting up with external neighbor the IP address of monitoring session, because this address must possess the accessibility in the full the Internet scope, so AS m must declare to comprise the network prefix of this address in route system;

Ipi _m: monitor m is used for setting up with inner neighbours the IP address of bgp session, because this address only needs can reach in AS m inside, private network address is adopted in suggestion, and in route system, does not declare to comprise the address block of this address;

c _m: the collaborative prefix (cooperatingprefix) of monitor m, AS m declaration, ipe comprised _mPrefix in the minimum network prefix of address space;

G _m: the non-set that is used to make up the general prefix (general prefix) of contract network of AS m, the set of the prefix except collaborative prefix of monitor m declaration just, G _m=I _m-{ c _m.

1. routing update monitoring method

This method detects the route updating packet from the monitoring neighbours, i.e. the detection of " control plane " is jumped kidnapping accident to find the BGP prefix hijack that is directed to this autonomous system with next.

Symbol description and term definition that this method relates to are following:

R: a route, be a doublet r=(d, p), wherein d is a network prefix, p is the AS-Path attribute of route, refers to that specifically local autonomous system arrives the autonomous system sequence of the required process successively of network d, is designated as [v _kv _K-1... v ₁v ₀].Propagate among the BGP routing update ' Announcement ' and ' Withdrawal ' two types arranged; Be designated as ' A ' and ' W ' respectively; The routing update of ' A ' type is corresponding to the AS-Path attribute of non-NULL, and the routing update of ' W ' type is corresponding to the AS-Path attribute of sky.

R.origin: the autonomous system of declaration network d in route system, when

The time, r.origin=v ₀

In r.firsthop: the route r communication process on the internet first of process be different from the autonomous system of r.origin;

The strategy of u: for I _uIn any prefix d, the strategy of u comprises the mapping relations strategy O between prefix and the proclaimers _u(d) and prefix and first jump the mapping relations strategy L between the AS _u(d).O _u(d) expression autonomous system u thinks the autonomous system set of having the right to declare prefix d, L _u(d) be allowed to direct autonomous system set of learning the route of prefix d from u among the AS neighbours of expression u, reflected the route output policy of u;

M _i[d]: from monitor M _iLocate the route of observed arrival prefix d;

OSet _u(d, t): at t constantly, u is from the observed the proclaimers's set to prefix d of each monitoring neighbours;

FSet _u(d, t): at t constantly, u jumps the set of autonomous system from first of the observed route to prefix d of each monitoring neighbours;

Prefix d is to M _iUnreachable (d ∈ I _u): monitoring neighbours M _iDo not go to the route of local autonomic system network d;

Prefix d accessibility forfeiture: show all monitoring neighbours M _i(1≤i≤n) does not go to the route of prefix d.

The detailed process of this detection method is: monitor server u receives monitoring neighbours M constantly at t _iSend about the route updating packet r of prefix d the time, carry out following steps:

(1) judges whether the prefix d that this route relates to is gathering I _uIn, if, the correlation of this route and this autonomous system then is described, continue (2--6), otherwise return;

(2) route r is carried out Context resolution, obtain this route corresponding A S-Path attribute r.p;

(3) if

This routing update is ' A ' type, this route is further resolved obtain r.origin attribute and r.firsthop attribute, and upgrade monitor M _iCorresponding information, M _i[d]=r;

(4) if

This routing update is ' W ' type, then

Simultaneously, mean M _iThe AS at place becomes unreachable to network prefix d, generates prefix d to M _iInaccessible alarm information;

(5) recomputate current time and jump set with next from the observed the proclaimers's set of each monitoring neighbours to prefix d, ${\mathrm{OSet}}_u(d,t)\←{\∪}_{i=1}^n\left(M_i\right[d].\mathrm{Origin});$ ${\mathrm{FSet}}_u(d,t)\←{\∪}_{i=1}^n\left(M_i\right[d].\mathrm{Firsthop});$

(6) detect the consistency that the source autonomous system and first that newly receives is jumped autonomous system and predefine strategy, if r.origin does not belong to O _u(d), then generate the prefix hijack alarm, if r.firsthop does not belong to L _u(d), then generate next and jump the abduction alarm, if OSet _u(d t) is sky or FSet _u(d is empty t), then generates prefix d accessibility forfeiture alarm.

2. session status monitoring method

This method is monitored through the communications status to the synergic monitoring session of setting up between a plurality of monitors, takes precautions against the route abduction that is directed to synergic monitoring network itself.This method is operated on ' datum plane ', and whether the data path of monitoring in real time between this monitor and the monitoring neighbours is normal, and when detecting the synergic monitoring session failed, starts method for diagnosing faults, infers to cause failure reasons.

The synergic monitoring session connects two not monitors of direct neighbor usually, sets up outside connect (ebgp-multihop) of BGP in multi-hop step, in itself with common not difference of bgp session.From the purpose of service battery's general character, each side of bgp session need be for safeguarding two timers, KeepAlive and HoldDown.According to the regulation of Routing Protocol standard RFC4271, each Fang Jun of bgp session need send a KeepAlive message to the opposing party in duration is the interval of KeepAlive; If any side of bgp session does not receive the KeepAlive message in duration is the interval of HoldDown, then with this session replacement.Being provided with of acquiescence, KeepAlive and HoldDown timer be respectively 60 seconds and 180 seconds.BGP safeguards that for each session neighbour (Finite State Machine, FSM), each state machine has six state: Idle to an independent finite state machine, Connect, Active, OpenSent, OpenConfirm and Established.Synergic monitoring session is from wherein a side, and its state is in " UP " and if only if that state machine is in " Established " state, and thinks all that when state machine is in other five states session is to be in " DOWN " state.

Between monitor u and its monitoring neighbours v through being based upon c _uAnd c _vBetween monitoring session exchange about prefix set I _uAnd I _vRouting update, but as prefix c _uOr c _vWhen being held as a hostage, can make the inefficacy of monitoring conversation and causing this monitoring method.Simultaneously, the routing failure on u → v or any direction of v → u also possibly cause monitoring session and is interrupted.

The concrete reason that causes the synergic monitoring session failure can be summed up as following four kinds of situation: the routing failure on (1) u → v direction is called the forward path fault; (2) routing failure on v → u direction is called the back to path failure; (3) the collaborative prefix of u is held as a hostage from v; (4) the collaborative prefix of v is held as a hostage from u.The reason of monitoring session failure possibly be the combination in any of above four kinds of factors under the real network environment.

The session status monitoring method is judged the operating state of contract network through the state of synergic monitoring session, and will work in coordination with the prefix (c that is held as a hostage _uOr c _vBe held as a hostage) the monitoring conversation that causes with routing failure makes a distinction, and realizes the accurate report and the location of routing safety incident.

Symbol description and term definition that this method relates to are following:

T: length is the time window of T, is traditionally arranged to be 3 KeepAlive or 1 HoldDown at interval;

S _i: with monitoring neighbours M _iThe synergic monitoring session of setting up, wherein S _i.State the state that refers to this monitoring session, i.e. " DOWN " or " UP ", S _i.fp refer to that u is to M _iThe path, be called forward path, S _i.bp refer to from M _iTo the path of u, be called the back to the path;

Ebuf _i: monitor u is each monitoring neighbours M _iSafeguard a buffer memory, store in the nearest T time from M _iThe monitoring session on observed incident, comprise BGP KeepAlive, the message that BGP Notification, TCP connect to set up and cancel and be relevant to prefix

Icmp packet.Each event definition is (time, type, an original message) tlv triple, and the original message of storage is used for the network manager and carries out depth analysis;

Bp _i: monitor u passes through the synergic monitoring session from monitoring neighbours M _iThe collaborative prefix c that acquires, oneself use _uThe AS-Path attribute of route, in fact this is exactly S _i.bp;

Monitor u safeguards following three kinds of states for its visible arbitrary network prefix d: (1) h _d: monitor u safeguards the path change of nearest a period of time that neighbours internally acquire for each network prefix d, each element be (t, path), wherein t is the time that receives routing update, path is the AS-Path attribute in the route updating packet that receives; (2) newp _d: current time monitor u is used to go to the AS-Path attribute of the optimum route of network prefix d; (3) oldp _d: T before the time monitor u be used to go to the AS-Path attribute of the optimum route of network prefix d;

Stable (h _d): according to h _dIn the current local autonomous system of information calculations to the AS-Path attribute of objective network d, and this AS-Path attribute before the T time.Concrete computational process is following: (1) is with h _dIn element arrange with ascending order according to time mark; (2) time difference between adjacent two elements of calculating; (3) choose two adjacent elements that generate maximum time difference, the AS-Path attribute of the element of less timestamp is made as oldp _d(4) with newp _dBe made as the AS-Path attribute of the element that maximum time stabs in all elements; (5) stable (h _d)=(oldp _d, newp _d);

E: incident Candidate Set, each element are (oldp _d, newp _d), the path of expression network prefix d is by oldp _dBecome newp _d

C: the fault Candidate Set, its element (u v) represents the limit between autonomous system u and the v, when u=v, represents the inner link of autonomous system u, each element (u, v) with a counter (u, v) .counter is associated, and representes the incident number that this link is relevant;

F: the fault collection, the link or the node of fault taken place in affirmation, is the sub-set of C.

The session status monitoring method is made up of two independent parts, and a part is responsible for upgrading and safeguarding the various states that monitored, and is called session status and safeguards submethod; Another part is analyzed the reason that causes changing when detecting session status and change, and generates daily record and carry out the network debugging with the auxiliary network keeper, is called session failure diagnosis submethod.The session status monitoring method only reads and does not change the running status of Routing Protocol, is independent of Routing Protocol in realization, need not make amendment to the route agreement.

2.1 session status is safeguarded submethod

Session status safeguards that submethod uses raw socket to monitor on monitor, when t receives IP message p constantly, carry out following steps:

The first step, " agreement " of obtaining the IP message be field (the 10th byte of IP message) (Protocol), resolves the source address field p that obtains message _Src

In second step, if ' agreement ' field is 1, then p is an icmp packet, otherwise returns; If the type code of icmp packet (type) is 3; Then the announcement of this message is " target is unreachable " abnormality, and read error code (code) extracts the destination address of the IP data that successfully are not sent to destination address that comprise in its data division; Be designated as b, otherwise return; If there is external neighbor M in monitor _i, make

Then carry out following steps, otherwise return:

(1) if this ICMP is " network is unreachable " (type code 3, error code 0), then to ebuf _iThe middle adding (t, ' network is unreachable ', p);

(2) if this ICMP is " main frame is unreachable " (type code 3, error code 1), then to ebuf _iThe middle adding (t, ' main frame is unreachable ', p);

(3) if this ICMP is " unknown network " (type code 3, an error code 6), then to ebuf _iThe middle adding (t, ' network is unknown ', p);

(4) if this ICMP is " unknown main frame " (type code 3, an error code 7), then to ebuf _iThe middle adding (t, ' main frame is unknown ', p);

(5) if this ICMP is " port is unreachable " (type code 3, error code 3), then to ebuf _iThe middle adding (t, ' port is unreachable ', p);

(6) if this ICMP is " TTL is overtime " (type code 11, error code 0), then to ebuf _iThe middle adding (t, ' TTL is overtime ', p);

(7) scan ebuf from front to back _i, only preserve the incident that nearest T received in the time, return afterwards;

In the 3rd step, if ' agreement ' field be ' 6 ' (TCP), and ' destination interface ' (Destination port) field of TCP part (TCP the 3rd, 4 byte partly) is 179, and then p is a BGP message, otherwise returns;

In the 4th step, ' type (Type) ' field of parsing BGP message (the 19th byte of BGP part) is designated as type;

In the 5th step, if type is 1 or 3 or 4, this message is a BGP Open message, or the KeepAlive message, or the Notification message, then carries out following processing:

(1) if p _SrcBe the inside neighbours of this monitor, i.e. p _Src==ipi _u, then return;

(2) if p _SrcBe the external neighbor M of this monitor _i, promptly Then at ebuf _iThe corresponding adding (t, ' BGPOpen ', p), or (t, ' BGP KeepAlive ', p), or (t, ' BGP Notification ', p);

(3) scan ebuf from front to back _i, only preserve the incident that nearest T received in the time, return afterwards;

In the 6th step, if type is 2, this message is BGP routing update (BGP Update) message, resolves the prefix list w that obtains cancelling _p, the prefix list a of declaration _p, and AS-Path attribute path _p

If the 7th step is p _SrcBe the inside neighbours of this monitor, i.e. p _Src=ipi _u, then carry out following processing:

(1) if Then for arbitrary network prefix d ∈ w _p, to h _dMiddle its up-to-date variation of adding

Show the route of going to network prefix d from local autonomous system t constantly its path attribute become

(2) if Then for arbitrary network prefix d ∈ a _p, to h _dMiddle its up-to-date variation (t, the path of adding _p), show the route of going to network prefix d from local autonomous system t constantly its path attribute become path _p

(3) for any network prefix d ∈ w that relates among the p _p∪ a _p, check and upgrade corresponding h _d, particularly, only keep the routing update that [t-T, t] received in the time, and former constantly last routing update that receives of t-T;

If the 8th step is p _SrcBe the external neighbor M of this monitor _i, promptly

Then carry out following processing:

(1) if

If c _u∈ w _p, then Show M from the monitoring neighbours _iTo the path of local autonomous system u, promptly the back is cancelled to the path;

(2) if

If c _u∈ w _p, bp then _i=path _p, show M from the monitoring neighbours _iPath to local autonomous system u becomes path _p

2.2 session failure diagnosis submethod

Session failure diagnosis submethod detects a session status to be changed, i.e. S _i.State:s _i→ s _i' (s _i≠ s _i') time, carry out following steps:

The first step is judged s _i' state, if " DOWN ", then continue to carry out; Otherwise be " UP ", return;

In second step, preliminary judgement causes monitoring session S _iFailure reasons

(1) calculates S _iForward path before losing efficacy, monitoring session S _i(the monitoring neighbours M of opposite end _iOne side) the IP address is

$S_i.\mathrm{Fp}=\mathrm{Stable}\left(h_{c_{M_i}}\right).{\mathrm{Oldp}}_{c_{M_i}};$

(2) calculate S _iBack before losing efficacy to the path, S _i.bp=bp _i

(3) monitoring session S _i(the monitoring neighbours M of opposite end _iOne side) the IP address is

If

In the AS-Path attribute of up-to-date element do

S then _iInefficacy cause that by the forward path fault forward path is S _i.fp;

(4) if ebuf _iIn have the ICMP incident, show M _iCollaborative prefix unreachable, S _iInefficacy cause that by the forward path fault this forward path is S _i.fp;

(5) check

If declaration prefix

AS variation has taken place, S then _iInefficacy because the collaborative prefix in opposite end is held as a hostage causes;

The 3rd step is if the equal unmet of condition in second step then causes S _iFailure reasons comprises local collaborative prefix c _uBe held as a hostage, or the back is to path failure.At first initialization

Then for each visible network prefix d of u, further diagnostic monitoring session S according to the following steps _iFailure reasons:

(1) according to h _dCalculate newp _dAnd oldp _d, (oldp _d, newp _d)=stable (h _d);

(2) if newp _d≠ oldp _d, in the incident Candidate Set, add incoming event e:oldp _d→ newp _d, be designated as E ← E ∪ { (oldp _d, newp _d);

(3) for two AS-Path that relate among the incident e, newp _dAnd oldp _d, at first remove the appearance (AS Prepending) that repeats continuously among every AS-Path, obtain shape such as v _kv _K-1... v ₁v ₀AS-Path (for 0≤m＜n≤k arbitrarily, v _m≠ v _n);

(4) in the fault Candidate Set, add ingress, Corresponding counter (the v of new node more _m, v _m) .counter ← (v _m, v _m) .counter+1;

(5) in the fault Candidate Set, add the limit,

Upgrade the corresponding counter (v in limit _M+1, v _m) .counter ← (v _M+1, v _m) .counter+1;

The 4th step, with the element among the fault Candidate Set C according to the value of its associated counter with descending, carry out following steps then:

(1) if

then from C, choose the highest element of Counter Value (x, y);

(2) for any one incident e:oldp among the E _d→ newp _d, if its oldp _dPerhaps newp _dAttribute comprises node or limit, and (x y), then removes it;

(3) incite somebody to action (x y) removes from C, if (x y) successfully removed one or more incidents from E, this link joined among the fault collection F, F ← F ∪ (x, y) };

(4) if

returns; Otherwise change (1);

In the 5th step, calculate node/limit and forward path S among the F _i.fp common factor F _Fp, and with the back to path S _i.bp common factor F _Bp

The 6th step, if

Then be the forward path fault, if

And ebuf _iIn no any BGP association message (only limiting to KeepAlive and Notification) in the 2T/3 time recently, then belong to afterwards to path failure, and return the fault collection F of non-NULL _FpOr F _BpIf above condition does not all satisfy, the local collaborative prefix of judgement is held as a hostage.

Adopt the present invention can reach following beneficial effect:

The present invention has made full use of the inner existing network management of AS, has measured facility; And public route data is issued the data acquisition facility that project is set up; Through working in coordination with and integrate existing Internet resources, make up monitoring BGP prefix hijack and jump the contract network of abduction with next.Adopt the present invention can obtain following effect:

(1) monitors the prefix hijack that is directed to this autonomic system network from control plane and jump kidnapping accident with next.Especially what deserves to be mentioned is that other routing safety monitoring method generally can only detect prefix hijack at present.From control plane these two types of incidents are detected that to have expense little, the characteristics that accuracy rate is high.

The communication of the bottom IP network that (2) the contract network operate as normal is relied on from datum plane is protected.The connective maintenance mechanism that is similar to bgp session is adopted in the synergic monitoring session, can guarantee not receive the interference of normal routing-events; Need not set up new stacking network and realize new stacking network agreement, dispose simple.Through condition monitoring to the synergic monitoring session, can diagnose the key node and the link that cause session status to interrupt, for the autonomous system keeper carries out the network debugging foundation is provided.

(3) because prefix hijack and next detection of jumping abduction are all carried out in this locality, do not exist the problem that security incident can't be notified victim's autonomous system that detects.The ISP that participates in public route data issuing service does not have the misgivings of data-privacy aspect, and directly benefits from the deployment of this method, has realized the unification of responsibility-power-benefit, helps the lasting expansion and the evolution of contract network scale.

Description of drawings

Fig. 1 is the deployment signal of the present invention in autonomous system;

Fig. 2 is the deployment signal of the present invention between autonomous system;

Fig. 3 is the route I/O strategy signal of monitor between inner neighbours and external neighbor;

Fig. 4 is a function module design of the present invention;

Fig. 5 has showed the concrete realization of this method on server;

Fig. 6 is quantity and the storage overhead that adopts the bgp update message that receives in per 3 minutes behind the present invention;

Fig. 7 is that an AS sets up the safe range that the synergic monitoring session can cover with the individual AS of 5n (1≤n≤11) respectively after adopting the present invention, to show the covering power of monitoring method of the present invention.

Embodiment

Fig. 1 is that monitor is at the inner interconnected sketch map of autonomous system (AS).From the purpose of backup, each monitor is preferably interconnected with two or above inside neighbours.The inner border router of AS exists multiple organizational form, comprises that employing iBGP is interconnected entirely, and Router Reflector and BGP are federal.According to the difference of mutual contact mode between the AS inner boundary router, the inside neighbours that monitor connected are also slightly different.(1) for the AS that adopts the complete interconnected border router of iBGP, shown in Fig. 1 (a), monitor need be with wherein two or above router be set up bgp session arbitrarily; (2) for the AS that adopts the route reflection deployment way; Shown in Fig. 1 (b), monitor need with wherein arbitrarily two or above Router Reflector (Route Reflector RR) sets up bgp session; And with monitor be configured to Router Reflector the client (Route Client, RC); (3) for the AS that adopts the federal deployment way of BGP, monitor only need add any federation wherein, and with this federation in any two or above router set up bgp session and get final product, connected mode identical with shown in Fig. 1 (a).

When monitor and inner neighbours are interconnected, when requiring monitor to set up bgp session, this method uses AS home address piece, and promptly this address block neither to outside autonomous system declaration, is also forbidden learning the route about this address block from outside autonomous system.This address block can be, but be not limited to privately owned address.Processing mode to the type address block is similar to the processing to AS internal router address, only propagates to provide this address block in the inner connectedness of whole AS through IGP in AS inside, still on the AS border, is filtered.The communication that can guarantee in this way between monitor and the inner neighbours is not held as a hostage.On implementation, autonomous system keeper can have multiple choices.For example, on border router, use route-map, filter-list, configuration means such as redistribute-list/prefix-list are filtered the address block that router uses; Perhaps, on border router, specific COMMUNITY attribute is filtered carrying out predefined COMMUNITY attribute on the route issue tense marker to BGP by IGRP.

Fig. 2 disposes signal between the territory of this method, deployment way has embodied the cooperative characteristics of this method between the territory, in the whole Internet scope, sees, thereby has disposed between the AS of monitor according to the interconnected peer-to-peer network that forms a monitor of self-defining strategy.Communicate based on TCP between the monitor, exchange mutual interested routing update.In principle, a monitor should be set up the synergic monitoring session with a plurality of monitors.

Different with the territory deployed is; In order to realize the communication between the monitor in the different AS territory; The network address that monitor is used for setting up with external neighbor the synergic monitoring session must be a routable on the Internet; In other words, the address block that comprises this address must and then be propagated in whole inter-domain routing system to AS neighbours' declaration, thereby has the accessibility in the network-wide basis.Usually, monitor only uses an address and outside all monitor neighbours to set up the synergic monitoring session, so that the state relation between a plurality of monitoring sessions during failure diagnosis.

Fig. 3 is the illustrative of I/O strategy under CISCO router form of monitor.

Each monitor neighbours inner with it in fact be within the compass of competency of same autonomous system, so the input and output strategy between them is simple relatively.Monitor need not add filtration ground and receive the route that all inner neighbours send over, and does not send any route to inner neighbours, the concrete configuration of monitor such as Fig. 3 first row secondary series; With other interconnected routers of monitor, promptly the inside neighbours of monitor need not add to monitor and filter all routes of ground output among the autonomous system u, and any route that the refusal monitor sends over, concrete configuration such as Fig. 3 first row the 3rd row.

For the monitor u and the v that are among the different AS, on u → v direction, u only limits to output about I _vThe route of prefix, simultaneously, v also only limits to input about I _vThe renewal of middle prefix.In like manner, v also only limits to output about I on v → u direction _uIn the route of prefix, u only imports about I _uThe routing update of middle prefix.To external neighbor output route the time, need be with the Local Preference in the route, Community and Med attribute all reset to sky or 0, and u and v concrete configuration are listed as with reference to the secondary series and the 3rd of figure 3 second row respectively.

Fig. 4 is the function module design of monitor, comprises the router/route software of bottom, management configuration module, monitor neighborhood configuration module, routing update monitoring modular, session status monitoring modular, network detection module and alarm module.The router of bottom/route software module specifically can adopt router device, also can adopt common server operating software router, and like Quagga, Zebra or XORP realize that it is used to upgrade with the interested separately network of monitor neighbours exchange.

Management configuration module realizes the function of two aspects.For any autonomous system u; At first; Autonomous system keeper need dispose monitor and carry out the necessary knowledge of synergic monitoring prefix hijack; Comprise the prefix sets that this autonomous system has, have direct-connected autonomous system neighbours, and each neighbour's prefix sets is given in declaration with this autonomous system.Moreover, also need dispose when this autonomous system monitor with other autonomous system in monitor when setting up session relationship, the supplementary that needs comprises security mechanism and the key of protecting session, and route input and output strategy.

The routing update monitoring modular is responsible for the BGP routing update from neighbours' monitor is checked, when finding to conflict with predefined knowledge existence, alarms to alarm module.The session status monitoring module is responsible for monitoring the state of the data communication between this monitor and the neighbours' monitor, when session is interrupted, alarms to alarm module.

Alarm module is from routing update monitoring module and session status monitoring modular receiving alarm information, and starts the network detection module warning information is confirmed, kidnaps when prefix and alarms to the autonomous system keeper after being identified.

The network detection module is used the current technological Ping that is widely used in topology probe, and TraceRoute and TCP Ping verify from datum plane the preliminary warning information of receiving.

Fig. 5 has showed the concrete realization of this method on server.Route software Quagga (http://www.quagga.net) that this realization employing is increased income and inner neighbours and external neighbor are set up the synergic monitoring session, and (Raw Socket) catches message through raw socket.Through optimization, routing update monitoring method and session status monitoring method have been merged to the message handling process.

Message to catching at first filters based on ' agreement '; Only keep ' ICMP ' and ' TCP ' type; If icmp packet is further resolved ' type of error ' and ' error code ', and the destination address of the IP message that causes based on the data division parsing of icmp packet makeing mistakes; If this destination address is certain external neighbor, then upgrade the corresponding ebuf of these neighbours; If this message is the TCP type, then further check whether BGP message of this message, if this message is the BGP message; Then need further to resolve the type (type) of this BGP message, when type is 2, this message is delivered to the routing update detection module detect the route abduction; Upgrade the back to the path by the session status monitoring method, if type is 1,3; 4, then directly deliver to the session status monitoring method and upgrade ebuf.

' vtysh ' that adopt Quagga self to provide to the state (communications status) of coordinated conversational on datum plane carries out; The order that this realization is adopted is that ' vtysh-e show bgp neighbors ' analyzes the state that extracts each monitoring session to the text that returns then.Periodic queries Quagga is to realize the real-time monitoring to session status, and polling cycle is made as 10s, when the state that detects the synergic monitoring session is not ' Established ', starts failure diagnosis.

Fig. 6 has showed the expense of synergic monitoring system.The data of using in the assessment come from the collector (route-views.routeviews.org) of the Oregon, America RouteViews of state university project, the BGP routing update that zero to 2010 is gathered from 39 ± 3 autonomous systems 31, on December 11: 59 when having chosen from January 1st, 2,010 zero.Particularly, suppose that monitor and this 39 ± 3 monitors of being assessed have set up the synergic monitoring session, mainly two indexs are assessed, the one, when T is made as 3 minutes of acquiescence, the BGP routing update quantity that monitor receives in T; The 2nd, when T is made as 3 minutes of acquiescence, the needed memory headroom of bgp update (in KB) that monitor storage T received in the time, the former mean value is 698.5/3 minutes, peak value 3661/3 minutes; The latter's mean value is 104KB, and peak value is 417KB.Consider flow in the core network now easily in Gb, and the internal memory of server, router reached more than the 2GB, these expenses can be born.

Fig. 7 shows when adopting three kinds of different strategies to choose the cooperation autonomous system of setting up the synergic monitoring session, the safe effect that can reach.Assessment has 33232 autonomous systems and 97485 limits that are connected different autonomous system based on real the Internet topology (being collected in the routing table of RouteViews project issue on January 1st, 2010).Suppose that u has disposed this synergic monitoring method, participated in the synergic monitoring network, when an AS kidnaps the prefix of u, just probably found by u.This method is defined as the AS set that the prefix of kidnapping u can be found by u for the safe range of u, and correspondingly, the size definition of safe range is the quantity of this type AS." randomized policy " is meant that u selects collaborative neighbours randomly; " the preferred connection " refers to that u always selects the collaborative neighbours of the maximum AS of the node number of degrees as oneself; " absolute utility " refers to that u always selects can be to the collaborative neighbours of the AS that oneself brings maximum safe range as oneself.Experiment shows that less than 35 o'clock, " absolute utility " strategy had significant advantage at collaborative neighbours' number of selecting, but after collaborative neighbours' number of choosing was above 45, the difference of three kinds of strategies on effect was also not obvious.The effect that this method is described is tactful and insensitive to choosing of node, allows the autonomous system keeper to choose the collaborative neighbours of this autonomous system neatly, has strengthened the flexibility of disposing.

Claims (5)

1. The collaborative monitoring method of guarding against border gateway protocol route hijacking, it is characterized in that, the technical scheme of this method is: the AS that participates in collaboration utilizes original or newly set up server to run BGP agreement, and one or more internal routers establish a user It is used to collect BGP sessions of routing update messages, and establish cooperative monitoring sessions with monitoring servers in multiple other ASs at the same time, and is specifically composed of two parts: a routing update monitoring method and a session state monitoring method. 2. the collaborative monitoring method of guarding against border gateway protocol route hijacking according to claim 1, is characterized in that, route update monitoring method detects the route update message from monitoring neighbor, namely the detection of " control plane ", to find For the BGP prefix hijacking and next-hop hijacking events of this autonomous system, the specific process of the detection method is: when the monitoring server u receives the routing update message r about the prefix d sent by the monitoring neighbor M _i at time t, it executes the following step: (1) Determine whether the prefix d involved in the route is in the set _Iu , if yes, then explain the relevance between the route and the autonomous system, continue (2--6), otherwise return; (2) Perform content analysis on the route r to obtain the AS-Path attribute r.p corresponding to the route; (3) if

The route update is of type 'A', further analyze the route to obtain the r.origin attribute and r.firsthop attribute, and update the information corresponding to the monitor M _i , M _i [d]=r; (4) if

The routing update is of type 'W', then

At the same time, it means that the AS where M _i is located becomes unreachable to the network prefix d, and an alarm message that prefix d is unreachable to M _i is generated; (5) Recalculate the announcer set and next hop set observed from each monitoring neighbor to prefix d at the current moment, ${\mathrm{OSet}}_u(d,t)\←{\∪}_{i=1}^{\mathrm{no}}\left(m_i\right[d].\mathrm{origin});$ ${\mathrm{FSet}}_u(d,t)\←{\∪}_{i=1}^{\mathrm{no}}\left(m_i\right[d].\mathrm{first\; shop});$ (6) Detect the consistency between the newly received source autonomous system and the first hop autonomous system and the predefined policy, if r.origin does not belong to O _u (d), generate a prefix hijacking alarm, if r.firsthop does not belong to L _u (d), then generate a next-hop hijacking alarm, if OSet _u (d, t) is empty or FSet _u (d, t) is empty, then generate a prefix d reachability loss alarm. 3. the collaborative monitoring method of guarding against border gateway protocol route hijacking according to claim 1, is characterized in that, session state monitoring method monitors the communication status of the collaborative monitoring session that is set up between a plurality of monitors, prevents against The route hijacking of the cooperative monitoring network itself, this method works on the "data plane", monitors in real time whether the data path between the monitor and the monitoring neighbor is normal, and starts the fault diagnosis method when the cooperative monitoring session is detected to be invalid, inferring that the the reason for the failure; The session state monitoring method consists of two independent parts, one part is responsible for updating and maintaining the various states monitored, which is called the session state maintenance sub-method; the other part analyzes the cause of the change when the session state change is detected, And generate logs to assist network administrators in network debugging, which is called the sub-method of session fault diagnosis; The session state monitoring method only reads and does not change the running state of the routing protocol, is independent of the routing protocol in implementation, and does not need to modify the routing protocol. 4. the collaborative monitoring method of guarding against border gateway protocol routing hijacking according to claim 1, is characterized in that, session state maintenance submethod uses original socket to monitor on monitor, receives IP message p at t moment , perform the following steps: The first step is to obtain the "Protocol" (Protocol) field (the 10th byte of the IP message) of the IP message, and analyze the source address field p _src of the message; In the second step, if the 'protocol' field is 1, then p is an ICMP message, otherwise it returns; if the type code (type) of the ICMP message is 3, then what the message notifies is the abnormal state of "target unreachable", Read the error code (code), extract the destination address of the IP data that is not successfully sent to the destination address contained in the data part, record it as b, otherwise return; if the monitor has an external neighbor M _i , make Then execute the following steps, otherwise return; (1) If the ICMP is "network unreachable" (type code 3, error code 0), add (t, 'network unreachable', p) to ebuf _i ; (2) If the ICMP is "host unreachable" (type code 3, error code 1), add (t, 'host unreachable', p) to ebuf _i ; (3) If the ICMP is "unknown network" (type code 3, error code 6), add (t, 'unknown network', p) to ebuf _i ; (4) If the ICMP is "unknown host" (type code 3, error code 7), add (t, 'host unknown', p) to ebuf _i ; (5) If the ICMP is "port unreachable" (type code 3, error code 3), add (t, 'port unreachable', p) to ebuf _i ; (6) If the ICMP is "TTL timeout" (type code 11, error code 0), add (t, 'TTL timeout', p) to ebuf _i ; (7) Scan ebuf _i from front to back, save only the events received in the latest T time, and then return; The third step, if the 'protocol' field is '6' (TCP), and the 'destination port' (Destination port) field of the TCP part (the 3rd and 4th bytes of the TCP part) is 179, then p is a BGP report text, otherwise return; The 4th step, the 'type (Type)' field (the 19th byte of BGP part) of parsing BGP message, is recorded as type; The 5th step, if type is 1 or 3 or 4, this message is BGP Open message, or KeepAlive message, or Notification message, then carry out the following processing: (1) If p _src is the internal neighbor of the monitor, that is, p _src == ipi _u , then return; (2) If p _src is the external neighbor M _i of the monitor, namely

Then add (t, 'BGPOpen', p), or (t, 'BGP KeepAlive', p), or (t, 'BGP Notification', p) to ebuf _i ; (3) Scan ebuf _i from front to back, save only the events received in the latest T time, and then return; Step 6, if the type is 2, the message is a BGP route update (BGP Update) message, and the resolved prefix list w _p , the announced prefix list a _p , and the AS-Path attribute path _p are obtained through analysis; Step 7, if p _src is the internal neighbor of the monitor, that is, p _src = ipi _u , perform the following processing: (1) If

Then for any network prefix d∈w _p , add its latest change to h _d

Indicates that the path attribute of the route from the local autonomous system to the network prefix d at time t becomes

(2) If

Then for any network prefix d ∈ _{a p} , add its latest change (t, path _p ) to h _d , indicating that the path attribute of the route from the local autonomous system to the network prefix d changes to path _p at time t; (3) For any network prefix d∈w _p ∪a _p involved in p, look up and update the corresponding h _d , specifically, keep only the routing updates received within [tT, t], and the ones received before time tT The last routing update arrived; Step 8, if p _src is the external neighbor M _i of this monitor, namely

Then do the following: (1) If

If c _u ∈ w _p , then

Indicates that the path from the monitoring neighbor M _i to the local autonomous system u, i.e. the backward path, is revoked; (2) If

If c _u ∈ w _p , then bp _i = path _p , indicating that the path from monitoring neighbor M _i to local autonomous system u becomes path _p . 5. The collaborative monitoring method for preventing border gateway protocol route hijacking according to claim 1, characterized in that, the session fault diagnosis sub-method detects a session state change, i.e. S _i .State: s _i → s _i '(s When _i ≠s _i ′), the following steps are performed: The first step is to judge the state of s _i ′, if it is "DOWN", continue to execute; otherwise, it is "UP", return; The second step is to preliminarily determine the cause of the failure of the monitoring session S _i (1) Calculate the forward path before S _i fails, and the IP address of the opposite end of the monitoring session S _i (monitoring neighbor M _i ) is

$S_i.\mathrm{fp}=\mathrm{stable}\left(h_{c_{m_i}}\right).{\mathrm{oldp}}_{c_{m_i}};$ (2) Calculate the backward path before S _i fails, S _i .bp=bp _i ; (3) The IP address of the opposite end of the monitoring session S _i (monitoring the neighbor M _i side) is like

The latest element in the AS-Path attribute is

Then the failure of S _i is caused by the failure of the forward path, and the forward path is S _i .fp; (4) If there is an ICMP event in ebuf _i , it indicates that the cooperative prefix of M _i is unreachable, and the failure of S _i is caused by a failure of the forward path, and the forward path is S _i .fp; (5) view

If the prefix is declared

The AS of s has changed, and the failure of S _i is caused by the hijacking of the coordinated prefix at the peer end; In the third step, if none of the conditions in the second step is met, the cause of S _i failure includes the hijacking of the local cooperative prefix c _u , or the failure of the backward path. Initialize first

Then for each network prefix d visible to u, follow the steps below to further diagnose the cause of failure of the monitoring session S _i : (1) Calculate newp _d and oldp _d according to h _d , (oldp _d , newp _d )=stable(h _d ); (2) If newp _d ≠ oldp _d , add event e to the event candidate set: oldp _d →newp _d , denoted as E←E∪{(oldp _d , newp _d )}; (3) For the two AS-Paths involved in the event e, newp _d and oldp _d , first remove the consecutive repeated occurrences (AS Prepending) in each AS-Path, and get the form v _k v _k-1 ... ... AS-Path of v ₁ v ₀ (for any 0 ≤ m < n ≤ k, v _m ≠ v _n ); (4) Add nodes to the fault candidate set,

Update the counter corresponding to the node (v _m , v _m ).counter←(v _m , v _m ).counter+1; (5) Add edges to the fault candidate set, Update the counter corresponding to the edge (v _m+1 , v _m ).counter←(v _m+1 , v _m ).counter+1; The fourth step is to arrange the elements in the fault candidate set C in descending order according to the values of their associated counters, and then perform the following steps: (1) If Then select the element (x, y) with the highest counter value from C; (2) For any event e in E: oldp _d → newp _d , if its oldp _d or newp _d attribute contains a node or edge (x, y), remove it; (3) Remove (x, y) from C, if (x, y) has successfully removed one or more events from E, add the link to the fault set F, F←F∪ {(x,y)}; (4) If

return; otherwise go to (1); The fifth step is to calculate the intersection F _fp of the nodes/edges in F and the forward path S _i .fp, and the intersection F _bp of the backward path S _i .bp; The sixth step, if

is a forward path failure, if

And there is no BGP-related message (only KeepAlive and Notification) in ebuf _i in the last 2T/3 time, it is a backward path failure, and returns a non-empty failure set F _fp or F _bp ; if the above conditions are not met , it is determined that the local cooperative prefix is hijacked.

Images