KR20090125754A - 무선 메시 및 센서 네트워크에서 탄력적 패킷 역추적을 위한 방법 및 시스템 - Google Patents

Abstract

네트워크에서 패킷 역추적을 위한 시스템 및 방법은 네트워크 내의 각 노드에 대한 아이덴티티 번호(ID)를 유지하는 것과, 회송 경로상의 각 노드와 싱크 사이에 공유된 비밀키를 이용하여 서명(예를 들면, 메시지 인증 코드(MAC))를 발생시키는 단계를 포함한다. 각 회송 노드는 자신의 ID와 서명을 결정론적 방법 또는 소정의 확률로 패킷에 첨부시킴으로써 마크를 남긴다. 싱크에서 패킷을 수신한 때, 각 패킷에 포함된 서명의 정확함이 상기 서명이 첨부된 순서의 역순으로 검증된다. 최종의 유효 MAC가 회송 경로에서 결정되어 오류 데이터 주입 공격에 결탁한 타협 노드의 위치를 결정한다.

Description

무선 메시 및 센서 네트워크에서 탄력적 패킷 역추적을 위한 방법 및 시스템{METHOD AND SYSTEM FOR RESILIENT PACKET TRACEBACK IN WIRELESS MESH AND SENSOR NETWORKS}

본 발명은 네트워크 통신에 관한 것이고, 특히 오류 데이터 주입을 식별 및 방지하기 위해 네트워크에서 역추적(traceback)을 행하는 시스템 및 방법에 관한 것이다.

패킷 역추적은 패킷의 참된 기점(true origin) 및 이 참된 기점이 네트워크에서 이동한 경로를 식별하는 기술이다. 이 기술은 최근 생겨난 서비스 거부(DoS) 공격과 싸우기 위해 널리 사용되고 있고, 여기에서 공격 패킷의 소스 어드레스는 일반적으로 공격자의 아이덴티티를 숨기기 위해 공격자에 의해 "날조"(forge)된다.

유선 인터넷용으로 다수의 IP 패킷 역추적 방식이 있다. 예를 들면, 확률적 패킷 마킹(probabilistic packet marking; PPM) 방식이 제안되어 왔다. 특정의 확률을 가진 PPM 방식에 있어서, 라우터는 라우터가 회송하는 패킷 내에 일부 정보를 "마크"한다. 이 정보는 라우터의 아이덴티티 또는 2개의 인접 라우터 간의 링크를 운반한다. 다른 라우터로부터 마킹을 수집한 후에, 수신지(destination)는 패킷이 이동한 경로를 재구성할 수 있다.

소정의 경로를 따르는 라우터의 아이덴티티에 의해 그 계수들이 결정되는 다항식(f(x))으로 경로 정보가 암호화되는 대수법이 제안되어 있다. 각 패킷은 샘플(x)을 소지하고, 경로를 따르는 모든 라우터들은 f(x)를 집합적으로 연산할 것이다. 충분한 (x, f(x)) 값 쌍을 수집한 후에, 수신지는 계수들을 파생시켜서 종국적으로 라우터들의 아이덴티티를 추론할 수 있다.

다른 기술로서, 각 라우터는 이전에 회송된 패킷들을 연장된 기간동안 저장하도록 요구된다. 라우터들이 과거에 하나의 패킷을 회송하였는지를 라우터에 질의함으로써, 수신지는 회송 경로를 재구성할 수 있다. 라우터들은 대역외(out-of-band) 역추적 메시지들을 작은 확률로서 소스 또는 수신지에 또한 전송할 수 있다. 이 메시지들의 수집은 수신지가 경로를 재구성하게 한다.

이 방식들은 제한된 위협 모델(threat model) 하에서 설계되었고, 많은 응용, 예를 들면 무선 메시 및 센서 네트워크에서 불충분하게 된다. 이러한 종래의 기술 대부분은 중간 노드(라우터)들이 타협(compromise)되지 않는 것을 가정한다. 이것은 실제에 있어서, 특히 노드들이 물리적 포착 및 타협에 대하여 상처입기 쉬운 무선 메시 또는 센서 네트워크에서 참(true)이 아닐 수 있다. 이러한 방식에서는 단일의 타협된 중간 노드마저도 패킷들의 참된 기점이 식별되지 못하게 할 수 있다. 타협된 노드는 마킹을 날조하여 피해자가 임의의 올바르지 않은 기점으로 역추적하도록 속일 수 있다.

또한, 많은 방식들은 다수의 패킷들이 수집될 것을 요구하거나, 중간 노드들이 다량의 감사 추적(audit trace)을 저장하여 가해자의 위치를 정확하게 적시하게 한다. 이러한 것들은 인터넷에서는 문제가 되지 않지만, 엄중한 대역폭, 에너지 및 기억 리소스를 가진 무선 메시 및 센서 네트워크에서는 심각한 실용상의 장애에 직면한다.

네트워크에서 패킷 역추적을 행하기 위한 시스템 및 방법은 네트워크 내의 각 노드에 대한 아이덴티티 번호(identity number; ID)를 유지하고, 회송 노드와 싱크 사이에 공유된 비밀키를 이용하여 결정론적 방법 또는 확률적 방법으로 각 회송 노드의 패킷에 부착되는 서명(signature), 예를 들면 메시지 인증 코드(MAC)를 발생시키는 단계를 포함한다. 패킷을 수신한 때, 싱크는 서명(MAC)이 추가된 순서의 역순으로 패킷 내의 서명(MAC)의 정확함을 검증한다. 최초의 무효 서명(MAC)은 날조된 보고서를 주입하였거나 급하게 합법적 패킷으로 장난친 타협 노드(compromised node)를 들추어낸다.

네트워크에서 패킷 역추적을 행하는 방법은 네트워크 내의 각 노드에 대한 아이덴티티 번호(ID)를 유지하는 단계와, 회송 노드와 싱크 사이에 공유된 비밀키를 이용하여 각 회송 노드에서 서명을 발생시키는 단계와, 싱크에서 패킷을 수신한 때, 서명이 추가된 순서의 역순으로 싱크에 의해 각 패킷의 서명들의 정확함을 검증하는 단계와, 회송 경로에서의 서명 유효성을 판정하여 오류 데이터 주입 소스 및/또는 결탁하는(colluding) 타협 노드의 위치를 결정하는 단계를 포함한다.

무선 메시 또는 센서 네트워크에서 패킷 역추적을 행하는 다른 하나의 방법은 네트워크 내의 각 노드에 대한 실제 아이덴티티 번호(ID)를 유지하는 단계와, 현재 노드와 싱크에만 알려진 비밀키에 기초하여 실제 ID로부터 익명(anonymous) ID를 연산하는 단계와, 회송 경로 내의 각 노드에 대한 비밀키를 이용하여 메시지 인증 코드(MAC)를 발생시켜서 적어도 2개의 확률을 가진 각 패킷을 마킹하는 단계와, 네트워크 내의 각 노드에 대하여 익명 ID로부터 실제 ID를 결정하고, 각 패킷에 존재하는 마크를 이용하여 노드 노선을 재구성하며, 실제 ID와 비밀키를 이용하여 회송 경로의 각 노드를 역으로 통하여 각 패킷의 MAC의 정확함을 검증하여 회송 경로의 최종 유효 MAC를 결정하는 것에 의해 오류 데이터 주입 소스를 찾아내기 위해 경로를 역추적하는 단계를 포함한다.

상기 및 기타의 특징 및 장점들은 첨부 도면과 함께하는 하기 예시적인 실시예의 상세한 설명으로부터 명백하게 될 것이다.

본 발명은 첨부 도면을 참조하여 양호한 실시예에 대한 하기의 설명에서 그 세부적인 사항이 제공될 것이다.

도 1은 일 실시예에 따른 무선 네트워크에서 각 노드의 회송 경로를 보여주는 도이다.

도 2는 수신된 패킷의 순서 번호가 허용가능한 한계 내에 있는지 여부를 판정하여 패킷이 합법적인 것인지 재생품인지를 검증하기 위해 현재 진행중인 순서 번호의 한정된 윈도우를 보여주는 도이다.

도 3은 본 발명의 원리에 따라 검출되는 결탁 소스 및 회송 몰(예를 들면, 타협한 노드)이 있는 회송 경로를 가진 예시적인 네트워크를 보여주는 도이다.

도 4는 본 발명의 원리에 따라 노드 순서를 재구성하는 예시적인 방법을 보여주는 블록/흐름도이다.

도 5는 본 발명의 원리에 따라 검출가능한 아이덴티티 교환에 의해 생성된 루프를 보여주는 도이다.

도 6은 3개 카테고리의 노드를 보여주는 도이다.

도 7은 회송 경로에서 유효 MAC를 가진 최종 노드를 보여주는 도이다.

도 8은 싱크가 x개의 패킷을 수신한 후 n개의 회송 노드 전부로부터의 마크가 수집되는 확률의 분석적 결과를 보여주는 그래프이다.

도 9는 싱크가 x개의 패킷을 수신한 후 n개의 회송 노드 전부로부터의 마크가 수집되는 확률의 시뮬레이션 결과를 보여주는 그래프이다.

도 10은 최초 x개의 패킷에서 싱크에 의해 마크들이 수집된 노드의 평균 갯수를 보여주는 그래프이다.

도 11은 40 노드 경로에 대하여 시간에 따른 후보 소스 집합 변화를 보여주는 그래프이다.

도 12는 100회의 시뮬레이션 동작중에서 얼마나 많은 시뮬레이션 동작이 소스를 총 경로 길이의 함수로서 명료하게 식별하는데에 실패하는지를 보여주는 그래프(이 그래프에서 200, 400, 600 및 800 곡선은 각 시뮬레이션 동작시 패킷의 수에 대응한다)이다.

도 13은 소스를 총 경로 길이의 함수로서 명료하게 식별하는 데에 필요한 패킷의 평균 갯수를 보여주는 그래프(여기에서는 각 시뮬레이션 동작시 800개의 패킷 이 싱크에서 수신된다)이다.

도 14는 예시적인 실시예에 따른 역추적 및 몰 배치를 위한 예시적인 시스템/방법을 보여주는 블록/흐름도이다.

실시예에 따르면, 복수의 결탁하는 가해자가 있는 경우 가해자 노드의 위치를 정확하게 적시할 수 있는 시스템 및 방법이 제공된다. 본 실시예는 위협이 더 심각하고 리소스가 더 엄격한 무선 메시 및 센서 네트워크에 대해 특히 적용가능하다. 종래 기술과는 대조적으로, 본 실시예는 타협된 노드뿐만 아니라 타협된 회송 노드의 존재하에 작용하여 그들의 위치를 적시한다. 이것은 날조된 마크를 방지하기 위해 마킹에 인증자를 추가하는 것 이상이다. 종래 기술에서 복수의 결탁하는 타협 노드들은 아직까지 피해자(victim)를 속여서 순수 노드(innocent node)를 추적하게 할 수 있다. 본 발명의 원리에 따르면, 더 적은 리소스를 이용하여 탄력적인 역추적이 달성되고, 역추적은 단일 패킷만을 이용하여 가해자(perpetrator)에 대하여 달성될 수 있다.

많은 무선 센서 네트워크들은 아마도 반대 즉 호의적이지 않은 환경에서도 작용할 것으로 기대된다. 그들의 수반되지 않은 동작(unattended operation) 때문에, 반대자(adversary)가 센서 노드를 물리적으로 픽업하여 타협시키고 비밀키를 비롯한 저장된 데이터를 획득하는 것이 용이하다. 이들 타협된 "몰"(moles)은 각종 유형의 공격을 발진시킬 수 있고, 그 중 중요한 것 한가지는 오류 데이터 주입이다. 하나의 단일 몰은 다량의 위조 트래픽을 주입시켜 싱크가 넘쳐나게 하여 응용 프로그램의 실패를 유도하고 회송 경로를 따라 에너지 및 대역폭 리소스를 소비하게 할 수 있다. 최근의 연구에 의해 이러한 떠돌아다니는 위조 메시지를 검출하여 드롭시키기 위한 다수의 방식이 제안되어 있다. 그러나, 이 방식들은 공격에 따른 피해를 경감시키기만 한다는 점에서 모두 수동적이다. 이 방식들은 공격의 근본 원인에 저항하여 근본 원인을 제거하는 능동적인 수단을 제공하지 않는다.

이하의 설명은 능동적 저항, 즉 몰을 센서 네트워크에 어떻게 배치할 것인지에 대하여 취급한다. 몰의 위치를 알고 있으면, 그 몰은 네트워크로부터 격리 또는 제거될 수 있고, 그에 따라서 공격의 근본 원인을 박멸할 수 있다. 몰의 배치는 큰 연구 도전요소이다. 첫째로, 라우터가 엔드 호스트보다 더 보호되고 비교적 더 신뢰받는 인터넷과 대조적으로, 센서 네트워크의 모든 센서 노드들은 반대자에 의해 동일하게 액세스가능하고 균일하게 비보호된다. 어떤 노드는 패킷을 회송할 수 있고, 상승효과를 얻을 수 있는 비교적 신뢰된 라우팅 하부구조가 없다. 둘째로, 몰들은 결탁할 수 있다. 몰들은 그들의 비밀키를 공유할 수 있을 뿐만 아니라 협동 방식으로 패킷들을 조작하여 그들의 흔적을 완전히 감출 수 있다. 이러한 조작 공격은 단순히 위조 트래픽을 증가시키는 것보다 훨씬 더 복잡하다. 인터넷에 대한 기존의 인터넷 프로토콜(IP) 역추적 방식은 이러한 결탁하는 몰들을 생각하지 못하고 그러한 공격하에서 비효율적으로 된다.

특히 유용한 실시예에 따르면, 오류 데이터 주입 공격시 결탁 몰을 배치하기 위한 네스티드 마킹(nested marking) 방식이 제시된다. 패킷 마킹은 패킷의 참된 기점을 추론하기 위해 사용된다. 노드는 자신이 회송하는 패킷에서 자신의 아이덴 티티를 마크한다. 싱크는 그러한 마크들을 수집함으로써 노선(route)을 추론할 수 있고, 그에 따라서 트래픽의 기점 위치를 추론할 수 있다. 패킷 마킹이 인터넷에서 사용되었지만, 결탁하는 센서 몰에 대한 그 적용성은 우리의 지식에 대해 학습된 적이 없다. IP 역추적에 대한 기존의 마킹 방식은 중간 결탁 몰에 의해 쉽게 물리쳐질 수 있고, 중간 결탁 몰은 마크를 조작하여 소스의 참된 기점 및 그 자체를 숨기거나, 또는 싱크가 순수 노드로 추적하게 한다.

현재의 네스티드 마킹 방식은 단일 패킷 역추적을 지원한다. 각각의 회송 노드는 그 마크가 이전의 모든 회송 노드의 마크들을 보호하도록 네스티드 방식으로 패킷들을 마크한다. 비록 결탁 몰이 마크들을 어떻게 처리하더라도 결탁 몰은 소스의 위치 또는 그 자신의 위치를 확실하게 드러낸다.

센서 네트워크에서 몰에 대한 사전 보안(proactive security)의 필요성은 몰들이 발진시킬 수 있는 각종 결탁 공격에 대하여 패킷 마킹의 프레임워크 내에서 시험된다. 패킷 마킹의 보안은 네스티드 마킹이 충분하고 필요한 것임을 포함하고, 만일 이전 노드의 마크 부분들이 (많은 외관상 명백한 설계에서처럼) 보호되지 않으면, 결탁 몰이 소스 및 자신의 위치를 숨기거나 또는 싱크를 속여서 순수 노드로 추적하게 할 수 있다. 네스티드 마킹의 효과는 여기에서 분석적 평가를 통해 보여진다.

본 발명의 원리에 따른 확률적 네스티드 마킹(PNM) 방식은 2가지의 기술, 즉 네스티드 마킹 기술과 확률적 마킹 기술을 이용하여 결탁 몰에 대하여 안전하고 효율적인 역추적을 달성한다. 네스티드 마킹은 단일 패킷 역추적을 지원한다. 각 회 송 노드는 패킷의 마크가 이전의 모든 회송 노드의 마크들을 보호하도록 패킷들을 네스티드 방식으로 마크한다. 비록 결탁 몰이 마크들을 어떻게 처리하더라도 결탁 몰은 소스의 위치 또는 그 자신의 위치를 확실하게 드러낸다. 확률적 마킹은 센서의 제약된 리소스에 적합하게 되도록 패킷당(per-packet) 오버헤드를 감소시킨다. 각 노드는 특정의 확률로 마크를 남기며, 따라서 패킷은 수 개의 마크만을 소지한다. 새로운 마크가 기존의 마크를 교체할 수 있는 인터넷 마킹 방식과는 달리, 새로운 마크는 패킷에 단순히 부착된다.

PNM의 효과 및 효율은 여기에서 분석적 평가와 경험적 평가를 통하여 증명된다. PNM은 약 50개의 패킷 내에서 고속 역추적을 가지며, 싱크는 몰에 최대 20개의 호프(hop)를 배치할 수 있다. 이것은 몰이 의미있는 양의 공격 트래픽을 주입할 수 있기 전에 몰이 포착될 것이기 때문에 몰이 유효 데이터 주입 공격을 발진시키는 것을 실질적으로 방지한다.

결탁 공격에 대하여 안전한 확률적 네스티드 마킹(PNM) 시스템 및 방법이 제공된다. 결탁 몰들이 마크를 어떻게 취급하더라도, PNM은 몰들을 하나씩 배치할 수 있다. 네스티드 마킹은 결탁 공격에 저항하기 위해 충분하고 필요하다. PNM은 예를 들면 약 50개의 패킷 내에서 고속 역추적을 또한 가지며, 싱크로부터 최대 20개의 호프까지 몰을 추적할 수 있다. 이것은 임의의 유효 데이터 주입 공격을 실질적으로 방지하고, 몰은 몰이 임의의 의미있는 양의 위조 트래픽을 주입하기 전에 포착될 것이다.

본 발명의 실시예들은 전적으로 하드웨어 실시예의 형태, 전적으로 소프트웨 어 실시예의 형태 또는 하드웨어와 소프트웨어 요소를 둘 다 포함하는 실시예의 형태를 취할 수 있다. 양호한 실시예에서, 본 발명은 비제한적인 예로서 펌웨어, 상주 소프트웨어, 마이크로코드 등을 포함하는 소프트웨어로 구현된다.

또한, 본 발명은 컴퓨터 또는 임의의 명령어 실행 시스템에 의해 또는 이러한 시스템에 접속하여 사용하기 위한 프로그램 코드를 제공하는 컴퓨터 사용가능 또는 컴퓨터 판독가능 매체로부터 액세스가능한 컴퓨터 프로그램 제품의 형태를 취할 수 있다. 이 설명의 목적상, 컴퓨터 사용가능 또는 컴퓨터 판독가능 매체는 명령어 실행 시스템, 장치 또는 기기에 의해 또는 이러한 기기에 접속하여 사용하기 위한 프로그램을 포함하거나 저장하거나 통신하거나 전파하거나 운송할 수 있는 임의의 장치일 수 있다. 매체는 전자식, 자기식, 광학식, 전자기식, 적외선식 또는 반도체 시스템(또는 장치 또는 기기) 또는 전파(propagation) 매체일 수 있다. 컴퓨터 판독가능 매체의 예로는 반도체 또는 고체 메모리, 자기 테이프, 제거가능한 컴퓨터 디스켓, 랜덤 액세스 메모리(RAM), 읽기 전용 메모리(ROM), 강성 자기 디스크 및 광 디스크가 있다. 현재의 광 디스크의 예로는 콤팩트 디스크-읽기 전용 메모리(CD-ROM), 콤팩트 디스크-읽기/쓰기(CD-R/W) 및 DVD가 있다.

프로그램 코드를 저장 및/또는 실행하기에 적합한 데이터 처리 시스템은 시스템 버스를 통해 메모리 요소에 직접 또는 간접적으로 결합된 적어도 하나의 프로세서를 포함할 수 있다. 메모리 요소는 프로그램 코드의 실제 실행 중에 사용되는 로컬 메모리, 대용량 기억장치, 및 실행중에 대용량 기억장치로부터 코드를 검색하는 횟수를 줄이기 위해 적어도 일부의 프로그램 코드를 임시 저장하는 캐시 메모리 를 포함할 수 있다. 입력/출력 즉 I/O 장치(비제한적인 예로서 키보드, 디스플레이, 포인팅 장치 등이 있음)는 직접 또는 중간에 I/O 제어기를 개재시켜서 시스템에 결합될 수 있다.

네트워크 어댑터가 시스템에 또한 결합되어 데이터 처리 시스템이 사설 또는 공중 네트워크를 통해 다른 데이터 처리 시스템 또는 원격 프린터 또는 기억 장치에 결합되게 할 수 있다. 현재 이용가능한 네트워크 어댑터 유형의 일부로서 모뎀, 케이블 모뎀 및 이더넷 카드 등이 있다.

이제 동일한 참조 부호가 동일한 요소 또는 유사한 요소를 나타내는 도면을 참조하면, 먼저 도 1에 도시된 바와 같이, 네트워크(10)는 복수개의 노드(12)를 포함하고 있다. 일부 노드(12)는 회송 경로(14)에 배치될 수 있다. 각 노드(12)는 키(K)를 싱크 노드(싱크)와 함께 공유할 수 있고, 단조롭게 증가하는 순서 번호(sequence number)를 유지한다. 소스 노드(소스)(A)가 메지지(M)을 송출할 때, 소스 노드는 자신의 ID 및 순서 번호를 첨부시키고, 그 다음에 서명(예를 들면, 메시지 인증 코드)를 연산한다. 소스는 패킷 전체를 다음 호프 노드(1)에 전송하고 그 순서 번호를 증분시킨다. 유사하게, 노드(1)는 자신의 ID 및 순서 번호를 첨부시키고 패킷에 대한 아직 남은 다른 서명를 연산하며, 그 결과를 다음 호프에 전달하고 그 순서 번호를 증분시킨다. 종국적으로 패킷은 싱크 노드(싱크)에 도착한다. 도착하는 패킷은 원래의 메시지(M) 뿐만 아니라 경로상의 모든 노드의 ID, 순서 번호 및 서명을 포함한다.

싱크 노드(싱크)는 패킷 내의 ID로부터 패킷이 지나갔다고 나타내는 요구된 경로(claimed path)를 알게 된다. 싱크는 최종 호프 노드로부터 시작해서 역순으로 이 경로를 검증한다. 경로상의 각 노드에 대하여, 싱크는 그 노드와 공유되는 키를 이용하여 서명을 재연산하고 패킷 내의 서명이 올바른 것인지를 검증한다. 싱크는 순서 번호가 유효한 것인지를 또한 검증한다. 서명과 순서 번호가 성공적으로 체크되면, 싱크는 그 이전의 호프에 대한 검증을 계속한다. 종국적으로, 싱크는 모든 서명/순서 번호가 올바르게 검증되었을 때 또는 최초로 올바르지 않은 서명/순서 번호가 나타났을 때 중지한다. 가해자 노드는 싱크가 검증을 중지한 노드의 1-호프 이웃 내에 있다.

우리가 서명을 연산하고 서명이 "양파껍질" 방식의 층별로(한번에 1층씩) 메시지를 보호하기 때문에, 검출되지 않고 이전 호프의 메시지를 날조하거나 변경할 수 있는 노드는 없다. 각 패킷이 호프마다의 순서 번호를 소지하기 때문에, 가해자는 검출없이 합법적인 구 트래픽을 재생할 수 없다. 복수의 결탁 노드가 있는 경우, 경로상에서 최종 가해자의 위치가 최초로 발견되고 두번째부터 마지막까지 순서대로 발견된다. 이들 노드가 위조 메시지의 주입 및 마킹의 조작을 계속하는 한, 그들의 위치는 하나씩 발견될 것이다. 이와 대조적으로, 기존의 해법은 타협된 중간 노드를 취급하지 못하거나, 복수의 타협 노드가 결탁할 때 보호를 제공하지 못한다.

본 발명의 원리에 따르면, 탄력적 역추적 방식은 복수의 타협된 노드에 의해 발진된 결탁 공격에 대하여 방어하기 위해 제공된다. 각각의 회송 노드는 서명을 사용하여 그 자신의 마크뿐만 아니라 이전의 모든 회송 노드로부터의 마크를 네스 티드 방법으로 보호한다. 이것은 결탁 노드가 있는 경우에도 타협된 공격 노드의 위치를 역추적할 수 있다. 일 실시예에 있어서, 결정론적 마킹이 사용된다. 그러나, 모든 회송 노드가 패킷에 마크를 남기기 때문에, 네트워크 사이즈가 대형으로 된 때 증가된 메시지 및 통신 오버헤드가 야기될 수 있다. 그러므로, 대안적인 실시예에서는 결탁 공격에 대한 보안적 방어를 보존하면서 패킷당 통신 오버헤드를 일정한 레벨로 감소시킬 수 있는 확률적 네스티드 마킹(PNM) 방식이 사용된다.

PNM 실시예에서는 각 회송 노드가 작은 확률(p)로 패킷을 마크한다. 그 결과, n개의 노드의 회송 경로상에서, 패킷은 평균적으로 n*p개의 마크만을 소지하는데, 이것은 대안적인 네스티드 마킹 방식에서 단순히 n개의 마크를 소지하는 것과는 대조적이다. 비록 외관상으로는 간단한 연장으로 되어 있지만, 이것은 2가지 문제 때문에 더 많은 것을 수반하는 것으로 된다.

첫째로, 네스티드 마킹 방식에 대한 상기 간단한 확률적 연장은 새로운 보안 루프홀(loophole)을 개방할 수 있다. 이것은 선택적인 드롭핑 공격에 대하여 상처를 입을 수 있고, 여기에서 타협된 회송 노드는 선택적인 패킷 집합을 드롭함으로써 그 자신과 참된 소스 사이에 임의의 순수 노드를 구성시킬 수 있다. 이러한 선택적인 드롭핑 공격을 물리치기 위하여, 익명화 기술을 사용하여 그들의 마크에 있는 노드 아이덴티티를 숨길 수 있다.

둘째로, 각 패킷은 완전한 경로의 부분 샘플링만을 소지할 수 있다. 경로 재구성 방법은 소수의 공격 패킷을 이용하여 경로를 재구성하기 위해 수신지에 대하여 제공된다. 수신지는 재구성된 경로를 사용하여 가해자 노드를 식별할 수 있다.

본 발명의 원리는 종래의 마킹 기술보다 훨씬 더 강한 방어를 제공할 수 있다. 본 실시예는 자신들의 흔적을 완전히 제거하기 위해 결탁하는 복수의 타협된 노드에 의해 발진되는 복잡한 선택적 드롭핑 공격을 포함한 각종 결탁 공격에 견뎌낼 수 있다. 양호한 실시예의 장점은 통신 오버헤드가 감소되고 확장성(scalability)이 개선된다는 점이며, 이것은 본 발명을 중간 규모 또는 대규모의 네트워크에 까지도 적용할 수 있게 한다.

다시 도 1을 참조하면, 경로 A-1-2...-Z-Z+1-...-싱크를 생각하자. 이 경로에서 A는 소스이다. 각 노드(12)는 키(K)를 싱크와 공유한다. 예를 들면, A는 K_a를 갖고 있고, 2는 K_2를 갖는 식으로 된다. 또한, 각 노드는 자신이 지금까지 발생하였거나 회송한 패킷의 수를 기록하는 순서 번호를 유지한다. 순서 번호는 노드(12)가 전개된 때 초기에 제로이고, 노드(12)가 패킷을 송출할 때마다 1씩 증분된다.

각 노드(12)는 단조롭게 증가하는 패킷 순서 번호를 또한 유지한다. A가 메시지(M)를 전송한 때, A는 자신의 아이덴티티와 순서 번호를 첨부시키고, 서명(예를 들면, 키 메시지 인증 코드(MAC))을 연산하며, 전체 패킷(M)을 다음 호프에 전송한다. 각 호프는 패킷을 다음 호프에 전달하기 전에 그 자신의 아이덴티티, 순서 번호 및 서명을 유사하게 첨부시킨다. 노드 A가 전송할 메시지(M)를 갖고 있을 때, A는 자신의 아이덴티티(A) 및 자신의 현재 순서 번호(seqnum)를 첨부시키고, 그 다음에 전체 메시지를 보호하는 서명을 연산한다:

A->B: M_a=M|A|seqnum|H_ka(M|A|seqnum) 여기에서 H_ka(x)는 키 K_a를 이 용한 x의 서명 연산을 나타내고, "|"은 연쇄(concatenation)를 나타낸다. 이 전체 패킷은 M_a로서 표시될 수 있다. A가 M_a를 다음 호프에 전송하고 자신의 순서 번호(seqnum)를 증분시킨다. 노드 1은 유사한 동작을 수행하고 다음 패킷을 노드 2에 전송한다: 즉, 1->2: M_a|2|seqnum2|H_k2(M_a|2|seqnum2) 등등으로 된다.

일반적으로, 경로상의 연속적인 2개의 노드(Z, Z+1)에 대하여, Z가 M_Z를 Z+1에 전송한 후, Z는 M_Z+1을 그 다음 호프에 M_Z+1=M_Z|Z+1|seqnumZ+1|H_k_Z+1(M_Z|Z+1|seqnumz+1)로서 전송한다. 싱크가 이러한 메시지를 수신한 때, 싱크는 패킷이 지나온 것으로 나타내는 요구 경로를 노드 ID로부터 검색할 수 있다. 싱크는 이 경로를 최종 호프 노드로부터 시작해서 패킷을 첨부한 순서의 역순으로 검증한다.

일반성을 상실하지 않고, 싱크가 노드 V를 검증하는 경우를 생각하자. 싱크는 M_Z|Z+1|seqnumz+1|H_k_Z+1(M_Z|Z+1|seqnumz+1)인 메시지 M_Z+1을 가진다. ID Z+1을 검색한 후, 싱크는 먼저 K_Z+1의 지식을 이용하여 서명이 올바른 것인지 여부를 체크한다. 그 다음에, 싱크는 순서 번호 seqnum z+1이 올바른 것인지를 검증한다. 이렇게 하기 위해, 싱크는 각 노드의 순서 번호의 슬라이딩 윈도우를 유지한다. 이것은 결정론적 마킹 실시예이다.

도 1과 함께 도 2를 참조하면, 각 노드(12)에 있어서, 현재의 윈도우(22)는 상부 경계(최대)와 하부 경계(최소)를 갖는다. 상부 경계(최대)는 이 노드로부터 수신된 최대 순서 번호이고, 하부 경계(최소)는 이 노드에 대하여 아직 유효한 최 소 순서 번호이다. 윈도우(22)는 수신되어야 할 유효이면서 무순서의 순서 번호가 아직 있는지를 유지한다. 각 패킷은 네트워크에서 최대 생존 시간을 갖는 것으로 추정되고, 이 최대 수명시간(T_max)을 이용하여 윈도우(22)를 갱신한다.

초기에, 최소 및 최대는 노드(12)가 전개될 때 둘 다 0이다. 싱크가 이 노드로부터 순서 번호가 d인 패킷을 수신한 때, 다음과 같은 3가지의 가능한 경우가 있다. 1) d<최소: 순서 번호가 이미 만료되었기 때문에 무효이다. 2) 최소≤d≤최대: 만일 d가 전에 수신되지 않았으면 d는 유효이고 마크가 d에 대하여 설정되어 d가 사용되었음을 표시한다. 싱크는 수신된 적이 없는 다음의 최소 유효 순서 번호로 최소치를 갱신한다. 그러나, d가 수신된 적이 있으면(예를 들어서 d가 마크되었으면), d는 재생이고 따라서 무효 순서 번호이다. 3) d>최대: 이 경우에, 순서 번호는 유효이다. 또한, 싱크는 최대=d로 설정하고, 순서 번호 d와 관련된 타이머를 시동시킨다. 타이머는 네트워크 내의 패킷의 최대 수명시간인 T_max 후에 만료될 것이다. 이 타이머가 만료되면, 싱크는 최소=d로 설정한다. 즉, d보다 작은 순서 번호를 가진 모든 패킷들은 네트워크에서 소멸되어야 한다.

경로상의 노드는 그 서명이 올바른 것이고 그 순서 번호가 유효한 경우에만 싱크 검증을 통과시킨다. 이 경우에, 싱크는 이전 호프의 ID를 검색함으로써 이전 호프의 검증을 계속하고 서명과 순서 번호를 검증한다. 종국적으로 모든 서명/순서 번호가 올바르게 검증되었거나 올바르지 않은 서명/무효 순서 번호가 발견된 때에 검증이 중지된다. 어느 경우이든, 타협 노드는 싱크가 중지한 곳으로부터 1-호프 이웃 내에 위치된다. 예를 들면, 싱크가 제1 호프 M|A|seqnuma|H(M|A|seqnuma)를 포함한 모든 노드를 정확하게 검증한 때, 실제 소스는 노드 A의 1-호프 이웃 내에 위치된다. 대안적으로, 만일 임의의 호프에서 서명 또는 순서 번호가 무효이면, 타협 노드는 무효 노드로부터 1-호프 이웃 내에 있다. 예를 들면, 호프 X: M_w|X|C_x|H를 검증한 경우, 싱크는 H가 H(M_w|X|C_x)와 일치하지 않는다는 것을 알아내고 타협 노드가 노드 X의 1-호프 이웃내에 있는 것으로 결론지을 수 있다. 즉, X가 가해자이거나(X가 불필요한 데이터(garbage) H를 의도적으로 날조함), Y와 같이 그 이웃중의 하나가 가해자이다(예를 들면, Y가 X의 서명 H를 수정하였지만 그 자신의 메시지에 대해 올바른 서명을 주었다).

제공된 보안성 보호는 많은 특징을 포함한다. 첫째로, 합법적 트래픽으로 조작한 가해자가 검출될 수 있다. 메시지는 서명에 의해 한층씩 보호되기 때문에, 메시지를 변경한 가해자는 소스로부터 시작해서 그 중간의 이전 호프까지 모든 이전 호프의 서명 체크가 실패하게 만들 것이다. 둘째로, DoS 공격 패킷을 주입하려고 하는 공격자는 키에 대한 지식을 갖고 있지 않기 때문에 원격의 기점을 정확히 위조할 수 없다. 싱크는 가해자 뒤의 정상 노드에 의해 남겨진 정보를 쫓아서 그 위치를 추적할 수 있다. 세째로, 메시지는 호프마다의 순서 번호에 의해 보호되기 때문에, 가해자는 이전의 합법적 트래픽을 재생할 수 없다. 그 이유는 가해자가 구 패킷의 증분된 순서 번호에 대한 올바른 서명을 만들 수 없기 때문이다. 복수의 공격 노드가 동일한 경로상에서 결탁하는 경우에도, 합법적 트래픽을 변경하거나 위조 트래픽을 주입하는 최종 가해자의 위치는 여전히 식별될 것이다. 싱크는 다른 노드에게 식별된 공격 노드와 통신하지 못하도록 추가로 지시할 수 있고, 나머지의 가해자 노드를 하나씩 찾아낼 수 있다.

모델 및 가정: 시스템과 위협 모델을 설명할 것이고, 부당한 공격의 분류가 패킷 마킹 프레임워크 내에서 제시된다.

도 3을 참조하면, 센서 노드(12)가 전개시 이동하지 않는 것으로 생각되는 정적 센서 네트워크(30)에 대한 시스템 모델이 도시되어 있다. 이 노드(12)들은 인접 환경을 감지하고 대상 이벤트에 대한 보고서(report), 예를 들면 이벤트의 시간, 위치, 설명 등(예컨대 센서 판독치)을 생성한다. 보고서는 중간 노드(41-47)에 의해 다중 호프 무선 채널을 통하여 싱크(38)에 회송된다. 싱크(38)는 충분한 연산 및 에너지 리소스를 가진 강력한 머신이다. 라우팅은 비교적 안정된 것으로 추정된다. 노선은 단기간 내에 빈번하게 변화하지 않는다. 노선이 안정된 때, 각 노드(12)는 회송 경로(36)에서 하나의 다음 호프 이웃만을 가지며 모든 패킷을 상기 이웃을 통해 싱크(38)에 회송한다. 이것은 이 기술 분야에서 공지되어 있는 임의의 트리 기반 라우팅 프로토콜 또는 지리적 라우팅 프로토콜과 일치한다.

각 센서 노드(12)가 유일한 ID를 갖고 유일한 비밀키(K)를 싱크(38)와 공유하는 것으로 가정하자. ID와 키는 노드가 전개되기 전에 노드(12)에 미리 로딩된다. 싱크(38)는 모든 노드의 ID와 키에 대한 조사표(lookup table)를 유지할 수 있다. 노드들이 이웃 인증과 같은 목적을 위해 다른 키를 형성할 수 있지만, PNM은 그러한 키가 작용할 것을 요구하지 않는다.

센서 노드(12)는 리소스가 제한될 수 있고 연산 능력, 기억용량 및 에너지 공급에 있어서 제한될 수 있다. 예를 들면, 공지의 Mica2 모트는 배터리에 의해 전 원이 공급되고 4MHz 프로세서 및 256K 메모리만이 설비된다. 이러한 저가격대(low-end) 기기에서는 공중키 암호작성법(public-key cryptography)이 구현될 수 있지만, 에너지 소모면에서 너무 비싸다. 따라서, 여기에서 설명의 간편성을 위해 효율적인 대칭 암호작성법(예를 들면 보안 해시 기능)만이 고려된다.

도 3의 예시적인 시나리오에서, 몰 S(소스(32))와 X(회송 경로 노드(44))는 함께 작용하여 공격 트래픽을 주입하기 위해 그들의 흔적을 완전히 제거하고, S는 위조 보고서를 주입한다. X(44)는 노드 1, 2, 3 마크(57)와 함께 패킷을 수신한다. X는 이 마크들을 1', 2', 3'(55)로 바꾸거나 또는 노드 1(56)의 마크를 제거하는 것과 같은 각종 방법으로 마크들을 조작할 수 있다. 몰의 목표는 그들의 위치를 숨기거나 순수 노드로 싱크 트랙을 유도하는 것이다.

위협 모델 및 공격 분류: 반대자는 물리적 포착 또는 소프트웨어 버그를 통하여 센서 노드와 타협할 수 있고, 따라서 센서 노드들의 완전한 제어를 얻는다. 반대자는 비밀키를 포함한 저장된 정보 모두에 액세스할 수 있고, 저장된 정보를 부당한 방법으로 행동하도록 재프로그램할 수 있다. 몰들은 피해를 최대화하도록 협조할 수 있다. 싱크(38)는 일반적으로 잘 보호된다. 비록 가능하기는 하지만, 타협된 싱크는 존재할 가능성이 매우 적으므로 설명의 간편성을 위해 고려하지 않겠다.

역추적의 경위(context)는 오류 데이터 주입의 위협이다. 하나의 몰(S)(32)은 소스로서 작용하고 네트워크에 대량의 위조 감지 보고서를 주입시킨다. 이러한 보고서는 사용자 응용을 방해할 뿐만 아니라 보고서를 회송할 때에 소비한 네트워 크 리소스(예를 들면, 에너지, 대역폭)를 낭비한다. 역추적은 적극적인 방어를 향한 제1 단계이다. 역추적은 싱크가 보고서의 참된 기점을 식별할 수 있게 한다. 싱크는 그 다음에 태스크 포스를 그러한 위치에 급송할 수 있고, 몰을 물리적으로 제거하거나 그들의 이웃에게 그들로부터 트래픽을 회송하지 말도록 통보할 수 있다. 정확한 메카니즘은 다를 수 있고, 현재의 포커스는 여기에서 역추적에 있다.

효과적인 마킹 방식에 대한 도전요소(challenge)는 마크에 의해 임의로 조작될 수 있는 회송 경로를 따르는 결탁 몰(X)(44)이다. 몰(X)(44)은 자신의 위치와 소스 몰(32)의 위치를 둘 다 숨길 수 있고, 또는 순수 노드에 대한 싱크 추적을 속일 수도 있다. 위치를 숨기면 포착되거나 응징받지 않고 연속적인 주입이 가능해진다. 이러한 숨기기는 주입에 의해 상당한 피해를 일으키기 위해 필요하다. 임의의 위치가 누설되면 네트워크 격리라든가 물리적 제거와 같은 응징을 받게 된다. 순수 노드에 대하여 싱크 추적을 속이는 것은 싱크가 순수 노드를 응징하는 추가적인 보너스이며, 따라서 타협되지 않은 리소스를 차단하고 그 자체를 효과적으로 응징하게 된다. 2개의 결탁 몰, 즉 위조 보고서를 주입시키는 S와 회송 경로상의 X에 의한 마킹 기반 역추적에 대한 결탁 공격의 분류는 다음과 같이 제공된다.

1) 마크없는 공격: 몰은 보고서를 전혀 마크하지 않는다. 2) 마크 삽입 공격: 소스 몰과 회송 몰은 둘 다 한개 또는 다수의 가짜 마크를 보고서에 삽입할 수 있다. 3) 마크 제거 공격: 회송 몰은 보고서 내의 상류 노드에 의해 남겨진 기존 마크를 제거할 수 있다. 4) 마크 재정렬 공격: 회송 몰은 보고서 내의 기존 마크를 재정렬할 수 있다. 5) 마크 변경 공격: 회송 몰은 보고서 내의 기존 마크를 바꿀 수 있고 그 마크들을 무효로 만들 수 있다. 6) 선택적 드롭핑 공격: 회송 몰은 싱크에 의해 수신된 경우 역추적을 그들에게 유도하는 그러한 패킷들을 선택적으로 드롭시킬 수 있다. 7) 아이덴티티 교환 공격: S와 X는 서로의 키를 알 수 있고 서로를 흉내낼 수 있다.

예를 들면, 도 3은 소스 몰(S)(32)과 싱크(38) 사이에서 7개의 회송 노드(41-47)의 연결을 보여주고 있다. 노드(X)(44)는 결탁 몰이다. 노드(44)는 노드(V₁, V₂, V₃)에 의해 남겨진 3개의 유효 마크(1, 2, 3)를 포함한 V₃'의 메시지를 수신한다. 노드(44)는 이들을 1', 2', 3'로 변경시켜서 이들을 무효로 만들 수 있고, 따라서 싱크는 이 마크들을 거부한다. 노드(44)는 마크 1을 제거하고 2, 3만을 남길 수 있으며, 따라서 역추적이 순수 노드에서 중지된다.

S	소스 몰
M	소스 몰(S)이 생성한 메시지. 이것은 이벤트, 위치, 타임스탬프를 포함한다. M=E|L|T
X	호프 x에서의 결탁 몰(Vx)
Vi	호프 1 내지 n에서 회송 노드
ki	Vi와 싱크 사이에 공유된 비밀키
Mi	노드 Vi에 의해 그 다음 호프 이웃 Vi+1에 회송된 메시지
mi	노드 i에 의해 Mi_1에 추가된 마크. 이 마크는 Vi'의 ID 및 MAC를 포함할 수 있다.

프리젠테이션을 돕기 위해, 표 1은 이하에서 사용되는 기호들을 포함하고 있다. 소스 몰(S)(32)은 합법적 형식과 일치하는 위조 보고서를 주입한다. 각 보고서(M)는 이벤트(E), 위치(L) 및 타임스탬프(T)를 포함하고 있다(즉, M=E|L|T이고, 여기에서 "|"는 연쇄를 의미한다). 보고서는 모두 동일한 내용을 정확하게 포함할 수 없고, 그렇지 않으면, 보고서는 여분의 것(redundant)으로 간주되어 합법적 회송 노드에 의해 드롭된다. M은 n개의 중간 노드{V_i}(i=1,...,n)의 연결을 통해 싱크(38)까지 회송된다.

각 노드(V_i)는 유일한 ID(i)를 가지며 유일한 키(k_i)를 싱크와 공유한다. 노드는 효율적이고 안전한 키 해시 기능 H_k()(여기에서 k는 키임)를 이용하여 자신이 발생하거나 회송한 패킷에 대한 메시지 인증 코드(MAC) 또는 다른 서명을 자신의 키를 이용하여 발생할 수 있다. 구체적으로 말하면, V_i는 마크 M_i를 자신이 이전 호프(V_i-1)로부터 수신한 메시지에 추가하여 그 자신의 메시지(M_i)를 구성한다. m_i는 V_i'의 ID(i)와 MAC(MAC_i)를 포함할 수 있다. 그 다음에 V_i는 M_i를 다음 호프(V_i+1)에 보낸다.

회송 노드 V_x(1＜x＜n)는 결탁 몰이고 X(44)로서 표시된다. X는 V_x-1로부터 수신한 메시지를 임의의 방법으로 조작한 다음 그 메시지를 V_x-1로 통과시킬 수 있다. 몰 X는 전술한 공격들 중 임의의 하나 또는 조합을 이용하여 S(32) 및 그 자신의 위치를 숨기거나 또는 순수 노드로의 역추적을 유도할 수 있다.

종래 기술의 인증 마킹 방식(AMS)은 노드에 의해 추가된 마크가 이전 노드에 의해 남겨진 마크에 대한 자신의 관계를 보호하지 못하기 때문에 충분한 보안성을 제공하지 못한다. 각 마크는 다른 마크의 유효성에 영향을 주지 않고 개별적으로 조작될 수 있다. 본 발명의 원리에 따른 네스티드 마킹은 각 마크와 모든 이전 마크 간에 묶음(binding)을 형성하고, 확률적 마킹은 추가적인 특징인 ID의 익명성을 제공하여 선택적 드롭핑 공격을 물리친다.

PNM은 단일의 의심되는 이웃의 정밀도 내에서 오류 데이터 주입 공격에 결탁 몰을 배치할 수 있다. 이것은 하나의 노드와 자신의 1-호프 이웃을 포함한다. 소스 몰이거나 회송 몰인 하나의 몰이 그들 중에 있다. PNM은 2개의 기술, 즉 네스티드 마킹과 확률적 네스티드 마킹을 포함한다. 네스티드 마킹은 기본적인 메카니즘이다. 이 기술은 싱크가 하나의 패킷만을 이용하여 임의의 몰에 역추적할 수 있게 한다. 그러나, 이 기술은 각 회송 노드가 패킷에 마크를 두어야 하기 때문에 메시지 오버헤드가 크다는 단점이 있다. 대형 센서 네트워크에서 이것은 효율적이지 않다.

이어서, 확률적 마킹을 이용하여 메시지 오버헤드를 복수의 패킷에 분산시킨다. 각 회송 노드는 특정의 확률로 마크를 배치한다. 따라서, 패킷은 단지 소수의 마크만을 소지하며 패킷당 오버헤드는 크게 감소된다. 이것은 더 낮은 메시지 오버헤드를 위해 검출 능력과 맞바꾸어진다. 싱크는 몰을 식별하기 위해 복수의 패킷을 필요로 할 수 있고, 이것은 몰들이 중대한 피해를 일으키기 전에 몰들이 식별되는 한 합리적이다.

기본적 네스티드 마킹: 패킷 마킹: 각 회송 노드(V_i)는 싱크와 공유하는 비밀키(k_i)를 이용하여 자신의 ID(i)와 보안 MAC를 패킷에 첨부한다. MAC는 V_i-1로부터 수신한 전체 메시지를 보호한다. 즉, MAC_i=H_ki(M_i-1|i)이다. 일 예로서, 이웃 노드에 의해 전송된 메시지는 다음과 같다.

S -> V₁:M

V₁ -> V₂:M₁ = M|1|H_k1(M|1)

V₂ -> V₃:M₂ = M₁|2|H_k2(M|2)...

V_i -> V_i+1:M_i = M_i|i|H_ki(M_i-1|i)

각 호프에서, ID(i)는 노선상의 노드 i의 존재를 나타내고, MAC H_ki(M_i-1|i)는 자신이 메시지(M_i)를 보낸 진정한 노드(i)인 것 및 노드가 수신한 것이 M_i-1이었다는 것을 싱크에게 증명한다. 노드는 V_i에 의해 추가된 MAC가 그 자신의 ID뿐만 아니라 이전 호프로부터의 전체 메시지라는 것을 알 수 있다. 이것은 네스티드 마킹의 이름이 온 곳이다. MAC는 모든 이전 노드의 ID 및 MAC와 그들의 상대적 순서를 보호한다. 이전의 ID 또는 MAC 또는 그들의 순서에 의한 임의의 조작은 MAC를 무효로 만들 것이다.

이하에서는 네스티드 마킹이 확실한 역추적을 위해 충분하고 필요하다는 것을 보이기 위해 공식적 보안 분석을 이용하겠다. 즉, 공식적 보안 분석은 모든 결탁 공격에 견뎌낼 수 있지만, 임의의 더 간단한 설계는 견뎌내지 못한다. 예를 들면, 확장된 AMS에서, 원래의 메시지(M)와 V_i의 ID는 보호되지만 마크의 묶음은 M_i-1의 이전 마크에 대하여 보호되지 못한다. 이것이 마크가 개별적으로 조작될 때 AMS가 실패하는 이유이다.

역추적: 패킷 M_n을 수신한 후, 싱크는 네스티드 마크를 역방향으로 검증한다. 싱크는 최종 호프(n)의 ID를 먼저 검색하고 대응키(k_n)를 이용하여 최종 MAC(MAC_n)를 검증한다. 만일 MAC_n이 올바른 것이면, 싱크는 이전 호프(n-1)의 ID를 검색하고 MAC_n-1을 검증한다. 싱크는 모든 MAC가 올바른 것으로 검증될 때까지, 또는 올바르지 않은 MAC를 발견할 때까지 이 과정을 계속한다. 몰(소스 또는 회송 몰)은 최종 검증된 MAC(이 노드 자체를 포함함)를 가진 노드의 1-호프 이웃내에 위치된다.

도 3의 예에서, 만일 몰(X)이 노드(41)의 마크를 변경하면, 노드(41, 42, 43)로부터의 마크가 모두 무효로 된다. X가 마크를 남기지 않거나 무효 마크를 남긴 경우, 역추적은 노드(45)에서 중단되고 몰(X)은 X가 유효 마크를 남긴 때 상기 중단된 노드의 1-호프 이웃 내에 있고, 역추적은 노드 X에서 중단하며 몰은 이 중단된 노드이다.

확률적 네스티드 마킹: 확률적 네스티드 마킹은 각 회송 노드가 패킷을 작은 확률(p)로 마크하게 한다. 따라서, n개 노드의 회송 경로에서, 평균적으로, 메시지는 np개의 마크를 소지한다. 확률(p)은 np개 마크의 오버헤드가 허용가능으로 되도록 조정될 수 있다.

부정확한 확장: 확률적 마킹에 대한 확장(extension)은 첫눈에 보았을 때 간단한 것으로 보일 수 있다. 그러나, 확률적 마킹에 대한 확장은 간단한 것이 아니다. 각 노드를 확률 p로 마크하는 것(뒤에서 설명함)은 역추적을 순수 노드로 유도할 수 있는 선택적 드롭핑 공격에 취약할 수 있다.

S -> V₁:M

V₁ -> V₂(p를 가짐):M₁ = M|1|H_k1(M|1)

V₂ -> V₃(1-p를 가짐):M₂ = M₁|2|H_k2(M|2)...

V_i -> V_i+1(p를 가짐):M_i = M_i-1|i|H_ki(M_i-1|i)

V_i -> V_i+1(1-p를 가짐):M_i = M_i-1 (1)

도 3의 예를 생각하자. ID 리스트가 평문으로 되어 있기 때문에, 결탁 몰(X)은 V₁, V₂, V₃ 중 어느 것이 패킷을 마크하였는지를 알 수 있다. 몰(X)은 V₁의 마크를 포함한 모든 패킷을 드롭할 수 있고, V₂, V₃로부터 S개의 마크를 가진 패킷들을 회송할 수 있다. 싱크가 역추적을 행할 때, 역추적은 1-호프 이웃이 어떠한 몰도 포함하지 않는 V₂에서 중단될 것이다. 실제로, X는 역추적을 그 자신과 소스 몰 사이의 임의의 순수 노드로 유도할 수 있다.

이 공격은 확률적 마킹에서 각 패킷이 회송 경로상의 노드의 일부 "샘플"만을 소지하기 때문에 동작을 한다. 평문 ID 때문에, 몰은 특정 "샘플"을 선택적으로 통과시켜 싱크가 X의 상류 노드중의 하나에서 종료하는 부분 경로를 보게 한다. 이 공격은 각 패킷이 완전한 경로를 구성하는 마크들을 소지하기 때문에 본 발명의 원리에 따라 기본적 네스티드 마킹(결정론적 마킹)에 적용하지 않는다. 선택적 드롭핑을 위한 부분 "샘플"은 존재하지 않는다.

선택적 드롭핑 공격을 물리치기 위해, 어떤 다른 노드가 패킷을 마킹했다는 것을 말할 수 있는 회송 노드가 없는 것이 바람직하다. 이 방법에서, 결탁 노드는 어느 패킷이 드롭되어야 하는지를 알 수 없다. 그러나, 싱크는 마크를 검증하기 위해 마크를 남겨놓은 자를 찾아낼 필요가 여전히 있다. 이하의 설명에서, 비대칭의 싱크를 이용하는데, 이것은 문제를 해결하기 위해 모든 비밀키에 대한 추가의 정보 및 충분한 연산 리소스를 제공한다.

확률적 네스티드 마킹: 합법 노드(V_i)는 실제 ID를 사용하는 대신에 패킷에서 익명의 ID(i')를 사용한다. 실제 ID(i)로부터 익명의 ID(i')로의 맵핑은 V_i 및 싱크에 의해서만 알려진 비밀키(k_i)에 의존한다. 결탁 몰은 타협되지 않은 V_i로부터 k_i의 지식을 갖지 못하고, 따라서 결탁 몰은 익명의 ID로부터 실제 ID를 추론할 수 없다.

S -> V₁:M

V₁ -> V₂(p를 가짐):M₁ = M|1'|H_k1(M|1'), 여기에서 1'=H'k1(M|1)

V₁ -> V₂(1-p를 가짐):M₁ = M...

V_i -> V_i+1(p를 가짐):M_i = M_i-1|i'|H_ki(M_i-1|i'), 여기에서 i'=H'ki(M|i)

V_i -> V_i+1(1-p를 가짐):M_i = M_i-1 (2)

상기 식에서, H'()은 익명의 ID를 연산하는 다른 하나의 안전한 1-방향 함수이다. 익명의 ID(i')는 M에 묶여져서 각각의 별도의 메시지(V_i) 회송을 위해 변화되게 한다. (여분의 카피로서 간주되거나 드롭되는 것을 피하기 위해 소스 몰에 의해 날조된 보고서는 다른 내용을 가져야 한다.) 이것은 공격자에 의해 시간에 따라 누적될 수 있는 정적 맵핑을 회피한다. 확장된 AMS와 비교하면, 확장된 AMS는 네스티드 마킹과 익명 ID를 둘 다 갖는다.

마크 검증: 싱크에서의 검증은 익명 ID 때문에 다르게 된다. 싱크는 먼저 실제 ID를 알 필요가 있고, 그 다음에 싱크는 대응하는 비밀키를 이용하여 MAC를 검증할 수 있다. 싱크에서의 풍부한 연산 능력은 실제 ID를 찾기 위해 철저한 조사를 사용하기 위해 이용될 수 있다.

노드(V_n)로부터 M_n을 수신한 후에, 싱크는 네트워크 내의 모든 노드의 모든 익명 ID를 먼저 연산한다. 싱크는 M을 알고 있으면 모든 ID(i~i')를 맵하기 위한 표를 구축할 수 있다. i'를 조사함으로써, 싱크는 실제 ID(i)를 알게 된다. 그 다음에, 싱크는 대응하는 키(k_i)를 사용하여 MAC를 검증할 수 있다. 이 방법으로, 싱크는 모든 MAC를 하나씩 검증할 수 있다. 철저한 조사는 주어진 싱크의 연산 능력 및 센서 네트워크의 낮은 데이터율을 실행할 수 있다. 각각의 별도의 메시지(M)에 대하여, 싱크는 조사를 위해 다른 표를 연산할 필요가 있다. 해시 연산이 마이크로초 수준에서 행해질 수 있다면(예를 들면, 1.6G CPU는 초당 250만 해시를 행할 수 있다), 상당히 큰 네트워크(예를 들면, 수 천개의 노드)용으로 이러한 표를 구축하는 것은 대략 수 밀리초가 소요될 것이다. 따라서, 싱크는 초당 수 백개 이상의 패킷을 검증할 수 있다. 싱크가 하나의 센서로부터 한번에 수신할 수 있기 때문에, 입력 데이터율은 센서의 라디오 비율에 의해 제한된다. 수 백개의 패킷은 전형적인 센서 하드웨어에서 현재의 실제 데이터율보다 이미 훨씬 더 높다(초당 100 패킷 하에서 Mica2 motes에 대하여 12kbps).

역추적: 몰의 배치는 2-단계 처리로 된다. 먼저, 싱크는 충분한 수의 패킷으로부터 마크를 수집하여 노선을 재구성할 필요가 있다(분석할 노드의 수는 뒤에서 취급할 것이다). 그 다음에, 싱크는 어느 노드가 그들의 1-호프 이웃에 몰을 갖는지를 식별한다. 확률적 마킹을 사용하는 몰을 싱크가 어떻게 배치하는지에 대하여 설명하는 예시적인 방법 1이 이하에서 의사 코드로 제공된다.

몰을 배치하기 위한 방법 1 알고리즘

도 4를 참조하면, 일 실시예에 따라서 몰을 배치하기 위한 시스템/방법에 대한 블록/흐름도가 도시되어 있다. 노선은 회송 경로에서 노드의 상대적 순서(노드에 대해 상류인 것)를 찾음으로써 재구성될 수 있다. 블록 110에서, 노선은 그 상류 노드 전부를 결정함으로써 재구성된다. 매트릭스(M)는 상대적 순서를 유지하기 위해 사용된다. 매트릭스는 초기에 비어있다. 새로운 노드(V_i)에 대한 올바른 MAC가 검증된 경우, V_i에 대응하는 하나 이상의 행 및 하나 이상의 열이 블록 112에서 매트릭스에 추가된다. 하나의 패킷 내의 2개의 연속적인 MAC(MAC_i, MAC_j)가 올바른 것으로 검증될 때마다, V_i는 V_j에 대하여 상류로 되어야 하고, M[i,j]는 블록 114에서 매트릭스에 이 관계를 기록한다(예를 들면, i와 j가 1로 설정된다. -1은 V_j가 V_i에 대해 상류임을 의미하고, 0은 미결정이다). 회송 경로상에 하나 이상의 노드가 있기 때문에, 복수의 노드가 확률 p로 코인을 플립(flip)할 때 복수의 노드가 패킷을 마크할 수 있었을 것이다(수학식 2 참조). 이 노드들은 경로상에서 연속적인 세그멘트가 아니어도 되고, 이 노드들은 회송 경로상에서 흩어져 있어도 좋다. 더 많은 패킷들이 수신된 때, 싱크는 이 매트릭스를 계속 갱신한다. 충분한 패킷이 주어진 때, 싱크는 모든 회송 노드 중에서 상류 관계, 즉 완전한 노선을 찾아낼 수 있을 것이다.

싱크는 2가지 유형의 노선, 즉 루프를 갖지 않은 노선과 루프를 갖는 노선을 재구성할 수 있다. 전자의 유형은 몰들이 아이덴티티 교환이 아닌 다른 공격을 사용할 때 발생하고, 후자의 유형은 몰들이 마크를 남기기 위해 그들의 아이덴티티를 교환할 때 발생한다. 첫번째의 경우에, 몰의 배치는 대부분의 상류 노드를 찾아내는 것과 등가이다. 소스 몰은 홀로 패킷을 생성하기 때문에, 소스 몰은 다른 것으로부터 패킷을 수신하지 않고 소스 몰은 최상류 노드일 수 있다. 회송 몰은 그 상류 노드에 의해 남겨진 마크를 제거한 경우 최상류가 되는 것으로 나타날 수 있다. 어느 경우이든, 소스 몰 또는 회송 몰은 최상류 노드의 1-호프 이웃 내에 있다.

몰은 아이덴티티 교환을 이용하여 루프를 생성할 수 있고(도 5 참조), 따라서 최상류 노드는 존재하지 않는다.

도 5를 참고하면, S와 X는 서로의 키를 이용하여 일부 패킷에 대한 유효 마크를 남길 수 있고, 따라서, 싱크가 노드들 간에 상류 관계를 재구성할 때 S와 X(이들 노드를 포함함) 사이의 모든 노드를 포함한 루프를 생성한다. 싱크는 링크에 대하여 루프가 파괴된 곳으로 여전히 역추적할 수 있고 그 이웃 내의 몰을 식별할 수 있다.

소스 몰(S)과 회송 몰(X)은 일부 패킷에 대해서 서로의 키를 이용하고 일부 다른 패킷에 대해서 그들 자신의 키를 이용하여 유효 마크를 남길 수 있다. 싱크는 S가 일부 패킷에 대해서는 X보다 앞에, 및 다른 패킷에 대해서는 X보다 뒤에 나타나는 것을 발견할 것이다. 싱크는 또한 S와 X 사이의 모든 노드(S와 X를 포함함)가 루프(130)를 형성하는 것을 발견할 것이다. 이러한 루프 내의 임의의 2개의 노드(U, V)에 있어서, U는 V에 대하여 상류 및 하류 둘 다에서 나타난다.

그러나, 이러한 변칙(anomaly)은 쉽게 식별될 수 있다. 즉 싱크는 나머지의 노드가 루프로부터 자신까지 라인을 형성하는 것을 발견할 수 있다. 몰은 이 라인에서 최상류 노드의 1-호프 이웃 내(즉, 루프가 라인과 교차하는 곳)에 배치된다.

보안 분석: PNM의 보안 강도는 대안적인 마킹 방식과 비교된다. 이 분석은 네스티드 마킹이 정밀하고 필요한 것임을 보여준다. PMN은 결탁 공격에도 불구하고 1-호프 이웃 영역 내에까지 몰을 추적할 수 있다. 확률적 네스티드 마킹은 싱크가 시간 경과에 따라 충분한 수의 패킷을 수신하기 때문에 1-호프 이웃 영역 내의 몰들을 점근선적으로 추적할 수 있다.

네스티드 마킹의 보안: 마킹 방식에 대한 2개의 속성, 즉 1-호프 정밀성(one-hop precision)과 연속 추적성(consecutive traceability)이 먼저 정의되고, 그 다음에 이들이 등가임을 증명한다. 그 다음에, 우리들의 기본적 네스티드 마킹 방식이 그 연속 추적성을 보임으로써 1-호프 정밀성이 있음을 증명한다.

정의 1(1-호프 정밀성): 마킹 방식은 소스 노드 또는 결탁 몰의 1-호프 이웃을 항상 추적할 수 있는 경우 1-호프 정밀성을 갖는다.

정의 2(연속 추적성): 회송 경로상의 2개의 연속적인 합법 노드(U, V)를 생각하자(즉, V는 U로부터 메시지를 수신하고, 그 다음에 이들을 회송한다). 연속추적가능 마킹 방식에 의해, 만일 싱크가 V까지 추적했다면, 싱크는 항상 U까지 추가로 추적할 수 있다.

법칙 1: 마킹 방식은 마킹 방식이 연속적 추적가능이면 1-호프 정밀성이 있다.

충분성 증명(Sufficiency Proof): 유효 MAC를 갖는 최종 노드(회송의 역순으로)인 노드(V)에서 역추적이 중단되는 경우를 생각하자. V는 회송 경로상에 없는 합법 노드일 수가 없는데, 그 이유는 그러한 노드가 그들이 회송하지 않은 메시지에 대한 MAC를 발생하지 않기 때문이며, 공격자는 그들의 비밀키를 알지 못한다. 따라서, V는 몰이거나 회송 경로상의 합법 노드이다. 만일 V가 몰이면 충분성(sufficiency)이 유지된다. 다음에, V가 합법적 회송 노드인 경우를 고려한다.

U를 V의 이전 호프라고 하자. 즉, V는 U로부터 메시지를 수신한다. 여기에는 U가 몰(소스몰 또는 결탁몰)이거나 또는 U는 합법 노드이다. 제1의 경우에, V가 몰 U의 이웃에 있기 때문에 충분성이 유지된다. 반면에, 연속 추적성의 정의에 의해, 역추적이 U로 진행할 것이고 V에서 중단되지 않을 것이다. 따라서, 제2의 경우는 발생하지 않는다. 이것은 충분성의 증명으로 귀결된다.

다음에, 필요성은 모순(contradiction)에 의해 증명된다. 마킹 방식은 연속 추적이 불가능한 것으로 가정한다. 즉, 싱크가 합법 노드(V)까지 추적하는 경우가 존재하지만, 이전의 합법 노드(U)로 진행할 수는 없다. 따라서, 역추적은 반드시 소스 또는 결탁 몰에서 중단할 필요없이 V에서 중단한다. 이 방식은 정의에 의해 1-호프 정밀성이 없다.

도 6을 참조하면, 회송 경로상에 2개의 노드 카테고리가 있다. 카테고리 1: 몰들과 이 몰들의 바로 다음의 호프; 카테고리 2: 바로 앞의 호프인 합법적 이웃을 가진 합법 노드. 연속 추적성 때문에, 역추적은 카테고리 2에서 중단할 수 없다. 카테고리 3 노드(회송 경로상에 없는 합법 노드)에 대하여, 이 노드들은 그들이 회송하지 않은 메시지에 대하여 마크를 남기지 않는다. 따라서, 역추적은 카테고리 1 노드에서만 중단할 수 있다.

1-호프 정밀성은 역추적이 제1 카테고리 내에서 중단하는 것을 의미하고; 연속 추적성은 역추적이 제2 카테고리 내에서 중단할 수 없는 것, 즉 역추적이 제1 카테고리 내에서 중단되어야 한다는 것을 의미한다.

법칙 2: 네스티드 마킹 방식은 연속 추적성이다.

증명: 2개의 연속적인 합법적 회송 노드(U, V)를 생각하자. M_u를 U가 V에게 보낸 메시지라고 하고, V는 M_u|V|H_kv(M_u|V)를 다음 호프에 보낸다고 하자. 싱크는 V까지 추적하였다고 가정한다. 이것은 싱크가 메시지 M'_u|V|MAC'_v에서 MAC'_v를 검증하였고 재연산된 MAC(H_kv(M'_u|V))가 내포 MAC'_v와 동일함을 알았다는 것을 의미한다. 공격자는 kv를 알지 못하기 때문에, MAC'_v는 V에 의해 생성된 MAC_v이어야 한다. 따라서, M'_u 및 M_u는 동일하여야 하며, 그렇지 않으면 재연산된 MAC는 V에 의해 성성된 것과 일치하지 않을 것이다. M_u는 합법 노드 U에 의해 보내지기 때문에, M_u의 최종 마크는 U로부터의 유효 MAC를 소지하여야 한다. 그러므로, 이 MAC를 검증함으로써 싱크는 추가로 U까지 추적할 수 있다.

추론 1: 네스티드 마킹 방식은 1-호프 정밀성이다.

네스티드 마킹의 필요성:

법칙 3: 네스티드 마킹보다 적은 필드를 보호하는 임의의 마킹 방식은 연속 추적성이 아니다.

증명: 네스티드 마킹에 있어서, 노드의 MAC는 그 자신의 ID, 및 노드가 이전 호프로부터 수신한 전체 메시지를 보호한다. 이제, MAC가 네스티드 MAC보다 더 적은 필드를 보호하는 대안적인 마킹 방식(r)을 생각하자. 노드의 ID 또는 MAC가 그 노드 이후의 모든 노드에 의해 완전하게 보호되지 않은 노드 A가 존재하여야 하고, 그렇지 않으면 r은 네스티드 마킹 방식으로 된다.

도 7을 참조하면, X는 V에 의해 보호되지 않은 A의 마크에 있는 비트들을 변경시킨다. 따라서, V의 마크는 아직 올바르지만, U의 마크는 올바르지 않다. 그러면, 싱크는 V까지 역추적하지만, U까지 추가로 추적할 수 없다. U는 A의 ID 및 MAC를 완전하게 보호하는 최종 노드로 되고, V는 U의 다음 호프가 된다(도 8 참조). 즉, A의 마크의 일부 비트는 V의 MAC에 의해 보호되지 않는다. V 다음에 하류의 1 몰을 생각하자. 이 몰은 보고서를 적절히 마크하고, A의 마크에서 V의 MAC에 의해 보호되지 않은 비트들을 변경시킨다. 이 경우에, V 다음의 모든 노드(V를 포함함)의 MAC는 올바른 것이고, 따라서, 싱크는 V까지 추적할 수 있다. 그러나, A의 마크가 몰에 의해 위조되기 때문에, U의 MAC는 무효로 나타나고, 따라서 싱크는 U까지 추가로 추적할 수 없다. 다시 말하자면, r은 연속 추적성이 아니다.

추론 2: 네스티드 마킹보다 적은 필드를 보호하는 임의의 마킹 방식은 1-호프 정밀성이 아니다.

확률적 네스티드 마킹의 보안:

법칙 4: 확률적 네스티드 마킹은 점근적으로 1-호프 정밀성이다.

증명: 싱크가 노드들 사이에서 상류 관계를 재구성할 때 2가지의 가능한 경우, 즉 루프가 없는 경우와 루프가 있는 경우가 있다. 루프가 없을 때, 증명은 법칙 2와 유사하다. 회송 경로상에 있는 2개의 연속적인 합법 노드(U, V)를 생각하자. 상기 2개의 노드는 확률적 마킹 때문에 항상 패킷에 마크를 남기지 않을 것이다. 그러나, 패킷의 수가 많기 때문에, 2개의 노드가 동일한 패킷에 함께 마크를 남기지 않을 확률은 패킷의 수(n)가 증가할 수록 점점 더 적어진다. 점근적으로, U와 V가 둘 다 마크를 남기는 패킷이 있을 것이다. 회송 몰은 그러한 패킷들을 드롭시킬 수 있다. 그러나, 익명 ID를 사용하기 때문에, 회송 몰이 항상 그러한 패킷들을 모두 올바르게 추측하여 드롭시킬 수는 없다. 점근적으로, 싱크는 U와 V로부터 마크가 있는 패킷을 수신할 것이다. 법칙 2에서와 유사한 이유에 의해, 일단 싱크가 V까지 추적하였으면 싱크는 U까지 추가로 추적할 수 있다. 따라서, 역추적은 V에서 중단하지 않을 것이다. 그래서, 역추적은 1-호프 이웃(이 노드 자체를 포함함) 내에서 몰을 가진 최상류 노드에서 중단해야 한다.

루프가 있을 때, 우리는 루프와 라인(도 6 참조)의 합류점(노드 X)이 그 1-호프 이웃(이 노드 자체를 포함함) 내에 몰을 가진 것을 모순에 의해 입증한다. 이 1-호프 이웃 내에 있는 4개의 노드(X, S, A, B)는 모두 합법 노드라고 가정한다. 패킷들이 싱크에서 X로부터 A까지 도달하기 때문에, A는 X의 회송 경로에서 다음 호프 이웃이어야 한다. 루프는 또한 노드들 간의 상류 관계를 나타내기 때문에, X는 루프에서 그 이웃 중의 하나(S 또는 B)에 패킷을 또한 회송하여야 한다. 그러나, 임의의 합법 노드는 노선이 안정된 때 그 회송 경로상의 단지 하나 다음 호프 이웃을 가져야 한다. 따라서, 상기 4개의 노드는 모두 합법 노드일 수 없고 그들중 하나는 몰이어야 한다.

이 증명 뒤의 직관(intuition)은 루프가 라인에 연결되는 곳 주변에서 어떤 비정상적인 행동이 있어야 한다는 것이다. 합법 노드에 있어서, 노드들은 노선이 안정된 때 루프를 형성하지 못한다. 따라서, 이러한 비정상적 행동은 몰의 존재에 의해서만 설명될 수 있다. 몰들은 기본적 네스티드 마킹에서 아이덴티티 교환 공격을 발진시킬 수 있지만, 모든 노드가 각 패킷에 마크를 남기기 때문에 싱크는 상류 관계를 통하여 역추적할 필요가 없고, 싱크는 항상 몰에 대하여 직접 역추적할 수 있다.

성능 평가:

싱크가 각각의 회송 노드(V₁,...V_n)로부터 적어도 하나의 마크를 수집하기 위해 필요로 하는 패킷의 수(N)를 분석하자. 우리는 이러한 분석이 L개의 패킷 내에서 행하여지는 확률을 연산할 수 있다. P(N≤L)=(l-l-p)^L)ⁿ

도 8을 참조하면, x개의 패킷 내에서 n개의 노드로부터 적어도 하나의 마크가 수집되는 확률을 보여주는 그래프가 도시되어 있다. 패킷이 소지하는 마크 np의 평균수는 3으로 고정된다. 10개의 노드를 내포하는 경로에 있어서, 싱크는 13개의 패킷을 수신한 후에 수집된 모든 마크의 약 90% 확률을 갖는다. 싱크는 20 및 30 호프의 경로에 대하여 각각 90% 신뢰를 달성하기 위해 33 및 54개의 패킷을 취한다. 그 결과, 상당한 에너지 및 대역폭 리소스를 낭비하지 않은 비교적 소수의 패킷 후에, 싱크는 모든 노드로부터 수집된 마크를 가질 것임을 보여주고 있다.

시뮬레이션 결과:

도 9를 참조하면, 분석을 검증하고 분석이 곤란한 메트릭에 대한 추가의 평가를 위해 시뮬레이션을 행한 결과가 도시되어 있다. 하나의 패킷이 평균적으로 3개의 마크를 소지하도록 상이한 경로 길이(n)에 대하여 확률(p)이 조정된다. 분석 결과가 먼저 검증되었다. 노드의 수(n)는 10, 20, 30으로 설정되었다. 각각의 시뮬레이션에서 소스로부터 200개의 패킷이 발생되었고, 우리는 5000회의 시뮬레이션의 결과를 평균하였다. 싱크가 x개의 패킷을 수신한 후에 모든 노드로부터의 마크가 수집되는 확률은 도 9에 도시되어 있다. 이 결과는 도 8의 분석 결과와 매우 일치한다.

도 10은 x개의 패킷 후에 마크가 싱크에 의해 수집된 노드 부분을 보여주고 있다. 10개의 노드가 있을 때 평균적으로 9개 노드의 마크가 7개의 패킷 내에서 수신될 수 있다. 20 및 30 노드의 경로에 있어서, 경로는 90%의 노드로부터 마크를 수집하기 위해 약 14 및 22개의 패킷을 취한다. 싱크는 수 십개의 패킷 중에서 어느 노드가 회송 노드인지를 안다.

확률적 마킹(방법 1)에서 노선 재구성 알고리즘의 성능이 또한 평가되었다.

도 11은 40-노드 경로(노드 0은 소스 몰임)의 시뮬레이션에 있어서 더 많은 패킷들이 수신된 때 후보 소스 집합이 어떻게 변화하는지를 보여주고 있다. 처음에, 노드 S는 후보 리스트에 있다. 더 많은 마크가 수신되기 때문에, 부분 경로의 시작시에 새로운 노드(8, 11, 9, 18)가 추가된다. 그들의 상류 노드가 나중에 발견되기 때문에, 노드들은 리스트로부터 제거된다. 실제 소스(0)는 21번째 패킷에 추가된다. 80번째 패킷 다음에는 0 이외에 집합 내에 남아있는 다른 후보 노드는 없다. 후보 집합이 장시간동안 변경되지 않고 유지된 때 싱크는 몰을 명료하게 식별할 수 있다.

충분한 수의 패킷이 없으면, 싱크는 후보 소스 집합을 단지 실제 몰까지 명료하게 감소시킬 수 없을 것이다. 얼마나 많은 패킷이 필요한지를 테스트하기 위해, 우리는 싱크가 수신하는 패킷의 수를 200, 400, 600 및 800으로 변경시켰다. 각각의 트래픽 양에 대하여, 우리는 5부터 50까지 10개의 상이한 경로 길이 각각에 대하여 100회의 시뮬레이션을 행하였다. 우리는 싱크가 소스를 명료하게 식별하지 않는 횟수가 얼마나 되는지를 알아냈다.

도 12는 4개의 상이한 트래픽 양에 대하여 실패한 동작의 수를 총 경로길이의 함수로서 나타낸 것이다. 최대 20까지의 경로 길이에 대하여 200개의 패킷이면 충분하다는 것을 알 수 있다. 방법 1은 각 동작의 소스를 거의 항상 명료하게 식별하고, 30까지의 경로에 대하여 400개의 패킷이면 충분하다. 매우 긴 경로(예를 들면, 50개의 노드)에 대해서만, 실패 빈도를 5% 미만으로 낮추기 위하여 많은 수의 패킷(예를 들면 800개)이 필요하다.

우리는 싱크가 소스를 명료하게 식별하기 위해 수신해야 하는 패킷의 평균수를 측정하기 위해 트래픽 양으로서 800을 선정하였다. 도 13은 소스를 성공적으로 식별한 모든 동작에 대하여 총 경로길이의 함수로서 그 결과들을 보여주고 있다. 20 미만의 경로 길이에 대하여, 소스를 명료하게 식별하기 위해 약 55개의 패킷을 취한다. 이것은 도 9의 결과와 대략 일치하고, 이 경우에는 55개의 패킷을 가지고 싱크가 20개의 노드 모두로부터 마크를 수집할 확률이 99% 이상으로 된다. 예를 들면 40개의 노드와 같이 긴 경로에 대해서도, 싱크는 약 220개의 패킷 후에 소스를 명료하게 식별할 수 있다. 그 결과 PNM은 몰이 유효 오류 데이터 주입 공격을 발진시키는 것을 거의 방지하는 것으로 나타났고, 몰은 몰이 네트워크에 대하여 충분한 피해를 일으키기 전에 배치될 것이다.

역추적 정밀성: PNM은 노드와 그 1-호프 이웃을 포함한 1-호프 이웃까지 몰을 역추적할 수 있다. 그들 중의 하나는 소스 몰이거나 회송 몰인 몰이다. 소스 몰은 보고서를 주입할 때 다른 아이덴티티를 요구할 수 있기 때문에 정밀성은 단일 노드가 아니다. 그 다음 호프 이웃은 어느 아이덴티티가 진정한 것인지 알 수 없다. PNM은 작용시킬 이웃들간의 페어와이즈 키(pairwise key)를 요구하지 않는다. 그러나, 페어와이즈 키가 있으면 역추적 정밀성을 개선하는데 도움이 된다.

PNM은 한번에 하나의 몰을 역추적한다. 일부 몰 격리 메카니즘이 PNM과 함께 작용할 것으로 기대된다. 몰 격리 메카니즘은 각 라운드에서 식별된 몰을 격리시킨다. 따라서, 시간이 경과함에 따라, 이 몰들은 네트워크로부터 하나씩 격리된다.

라우팅 다이나믹의 충격: 몰 배치 알고리즘은 노선이 비교적 안정된 때 잘 작용한다. 몰은 일반적으로 피해를 최대화하기 위해 단시간에 다량의 트래픽을 주입하므로, 충분한 패킷을 수집하는 데에 너무 많은 시간을 필요로 하지 않는다. 예를 들어서 몰이 최대 라디오율로 주입하면, 10초 이내에서 싱크는 몰을 40 호프 떨어져서 배치하기에 충분한 약 300개의 패킷을 수집할 수 있다. 노선은 이러한 짧은 시간 기간동안 안정 상태로 유지될 가능성이 매우 높다.

보고서 재생: 소스 몰은 동일한 콘텐츠를 가진 보고서를 복수회 재생할 수 있고, 따라서 각각의 회송 노드에 대하여 실제 ID와 익명 ID 간의 맵핑은 고정된 상태로 유지될 것이다. 결탁 몰은 시간이 경과함에 따라 그러한 맵핑을 누적할 수 있지만, 그러한 공격은 용장 메시지의 국부적 억제에 의해 쉽게 방해될 수 있다. 회송 노드는 동일한 콘텐츠의 보고서를 단순히 드롭할 수 있다. 이것은 최근에 본 메시지의 콘텐츠(즉, 이벤트, 위치 및 타임스탬프)의 서명(예를 들면, 해시 결과)을 유지하고 그들에 대하여 수신된 것들을 비교함으로써 행하여질 수 있다.

소스 몰은 실제 보고하는 소스 노드로부터 합법적 보고서를 또한 재생할 수 있다. 보고서 콘텐츠는 아직 올바른 정보를 제시한다. 그러한 메시지를 검출 및 드롭하기 위해, 동일한 국부적 억제를 사용할 수 있다. 다른 기술들이 또한 존재한다. 그들 중의 하나는 노드가 전송하거나 회송하는 각 메시지에 대하여 각 노드가 증가하는 순서 번호를 유지하게 하는 것이고, 각 노드는 마크의 일부로서 순서 번호를 포함하고 MAC를 이용하여 순서 번호를 보호한다. 싱크는 재생된 패킷이 동일한 순서 번호를 갖는 것을 검출할 수 있다. 이 기술은 위에서 설명하였다.

각 노드가 다른 키를 사용하기 때문에, 2개의 다른 노드의 익명 ID는 일치하지 않을 수 있다(예를 들면, H'_ki(M_u|i)=H'_kj(M_u|j). 암호작성법적으로 건전한 해시 기능은 그러한 불일치를 최소화할 수 있고, 불일치가 발생하였을 때 싱크는 그러한 패킷들을 검증으로부터 단순히 배제시킬 수 있다. PNM에서, 몰들은 더 많은 위조 마크를 삽입하거나 지시된 것보다 더 높은 확률을 이용하여 더 높은 패킷당 오버헤드를 또한 줄 수 있다. 그러나, 이것은 효율에 있어서 약간의 감소만을 일으키고, 싱크는 여전히 그들에게까지 역추적할 수 있다.

모두가 공격 트래픽을 전송하는 복수의 소스 몰이 존재할 수 있다. 기본적 네스티드 마킹은, 경로상의 모든 회송 노드의 마킹 때문에, 여전히 그들을 식별할 수 있다. 복수의 소스 몰의 회송 경로가 흩어진 때, PNM은 다른 경로들을 개별적으로 구성하고 몰들을 배치할 수 있다. 이 몰들은 또한 그들의 아이덴티티를 교환하여 루프를 생성할 수 있지만, 싱크를 루프에 연결하는 직선을 이용하여 상기 몰들을 한번에 하나씩 식별할 수 있다.

도 14를 참조하면, 무선 네트워크에서 역추적을 위한 시스템/방법의 블록/흐름도가 도시되어 있다. 노드의 네트워크에서, 각 노드는 아이덴티티 번호(ID)(선택적으로 도 2를 참조하여 위에서 설명한 순서 번호)가 할당되고 그 아이덴티티 번호를 유지한다(블록 202). 블록 204에서, 일 실시예로서, (실제) ID가 현재 노드와 싱크에 의해 또는 다른 수단에 의해 알려진 키를 이용하여 ID로부터의 익명 ID에 선택적으로 맵된다. 익명 ID의 맵핑은 회송된 각 메시지에 대한 익명 ID를 변경시키기 위해 현재의 패킷 메시지를 이용하는 것을 포함한다. 맵핑은 각 패킷마다 맵핑이 바뀌도록 패킷의 콘텐츠를 사용하여야 한다. 이것은 공격자에 의한 학습에 의해 누적될 수 있는 정적 맵핑을 회피한다. 이것은 PNM 실시예에서 양호한 것이다. 블록 206에서, 노드와 싱크 사이에 공유된 비밀키를 이용하여 서명, 예컨대 메시지 인증 코드(MAC)를 연산 또는 다른 방식으로 결정한다. MAC는 회송 경로를 통과한 각 패킷마다 결정된다. 블록 208에서, 이전 노드로부터의 패킷 또는 메시지는 상기 키에 따라 해시되어 MAC를 발생할 수 있다. MAC는 패킷 내의 수신 메시지의 해시된 버젼을 포함할 수 있다. ID는 회송 경로에 노드가 존재함을 표시하고, MAC는 ID와 관련된 패킷을 노드가 전송하였음을 입증한다.

패킷들은 블록 209에서 마크된다. 해시된 버젼은 패킷의 마킹을 생각할 수 있고, 마크된 패킷은 회송 경로를 통과하는 노드 순서를 제공하기 위해 나중에 사용된다. 패킷에 항상 마크를 두는 대신에, 회송 노드는 확률 p로 패킷을 마크한다. 회송 노드는 보통 때와 같이 그 익명 ID 및 MAC를 추가한다. 확률 1-p로, 회송 노드는 아무일도 하지 않고 단순히 패킷을 다음 호프로 회송한다. 다음 호프는 동일한 확률(p)을 이용하여 마크가 추가되었는지 여부를 결정하거나, 또는 단순히 패킷을 보통 때처럼 계속하여 통과시킨다. 마킹의 변형체는 각 노드가 마크를 두는 경우인 기본적인 결정론적 마킹, 및 각 노드가 특정 확률로 마크를 두는 경우인 확률적 마킹을 포함할 수 있다.

블록 210에서, 패킷은 회송 경로를 통하여 싱크에서 수신된다. 싱크는 충분한 수의 패킷에 대한 마크에 기초해서 노드의 순서를 재구성한다(블록 211).

싱크에서 각 패킷을 수신하면, MAC의 정확함이 회송 경로의 각 노드를 통하여 역으로 검증된다. 회송 경로 내의 최종 유효 MAC는 오류 데이터 주입 소스를 결정하기 위해, 또는 전체 경로가 검증되었다(예를 들면, 오류 주입 소스가 없다)는 것을 결정하기 위해 사용된다. 이것은 블록 214에서 최종 호프 노드의 ID를 검색하는 것, 블록 216에서 최종 호프 노드의 MAC를 연산하는 것, 블록 218에서 최종 호프 노드의 MAC를 검증하는 것, 및 블록 220에서 최종의 유효 MAC가 결정될 때까지 반복하는 것을 포함할 수 있다. 블록 216과 218은 도 2에서 설명한 슬라이딩 윈도우를 사용하여 순서 번호를 검증할 수 있다. 일 실시예로서, 블록 213에서, 실제 ID는 MAC를 검증하기 전에 회송 경로의 각 노드(또는 모든 노드)의 익명 ID로부터 결정된다.

블록 222에서, 최종의 유효 MAC는 1 호프 내에서의 몰의 배치를 표시한다. PNM에서 노선 재구성(예컨대 도 4 참조)은 몰을 배치하기 위해 수행될 수 있다. 도 4의 노선 재구성은 기본적인 결정론적 마킹 방식에 있어서는 필요없다. 몰은 회송 경로에 배치되고 블록 224에서 회송 경로로부터 제거된다. 특별히 유용한 실시예로서, 몰들은 회송 경로에서 복수의 결탁 몰을 포함한다. 이 몰들은 소스 노드 또는 회송 노드일 수 있고, 공격의 유형은 마크 삽입 공격, 마크 제거 공격, 마크 재정렬 공격, 마크 변경 공격, 선택적 드롭핑 공격, 아이덴티티 교환 공격 또는 임의의 다른 공격을 포함할 수 있다. 유리하게도, 몰들은 몰의 1 호프 내에서 본 발명의 원리에 따라 배치될 수 있다.

Claims (10)

1. 네트워크에서 패킷을 역추적하는 방법에 있어서,

   네트워크 내의 각 노드의 아이덴티티 번호(ID)를 유지하는 것과;

   각 회송 노드에서 이 노드와 싱크 사이에 공유된 비밀키를 이용하여 서명을 발생시키는 것과;

   싱크에서 패킷을 수신한 때, 각 패킷의 서명의 정확함을 서명이 추가된 순서의 역순으로 싱크에 의해 검증하는 것과;

   회송 경로의 서명 유효성을 결정하여 오류 데이터 주입 소스의 위치 및/또는 결탁하는 타협 노드의 위치를 결정하는 것을 포함하는 패킷 역추적 방법.
2. 제1항에 있어서, ID는 회송 경로 내의 노드 존재를 표시하고, 서명은 노드가 ID와 관련된 패킷을 전송하였음을 입증하는 것인 패킷 역추적 방법.
3. 제1항에 있어서, 키에 따라서 이전 노드로부터의 패킷을 그 전체로서 해시하여 서명을 발생시키는 것을 더 포함하는 패킷 역추적 방법.
4. 제1항에 있어서, 서명 유효성을 결정하는 것은 최종 호프 노드의 ID를 검색하는 것과; 최종 호프 노드의 서명을 연산하고 최종 호프 노드의 서명을 검증하는 것과; 최종의 유효 서명이 결정될 때까지 반복하는 것을 포함하는 것인 패킷 역추 적 방법.
5. 제1항에 있어서, 아이덴티티 번호(ID)를 유지하는 것은 현재 노드 및 싱크에 의해 알려진 키를 이용하여 ID로부터의 익명 ID를 맵핑하는 것을 포함하는 것인 패킷 역추적 방법.
6. 제1항에 있어서, 회송 경로를 통과하는 노드 순서를 제공하기 위해 패킷을 마킹하는 것을 더 포함하는 패킷 역추적 방법.
7. 제1항에 있어서, 각 패킷의 서명의 정확함을 검증하는 것은 슬라이딩 윈도우를 이용하여 유효 순서 번호를 결정하는 것을 포함하는 것인 패킷 역추적 방법.
8. 제1항에 있어서, 회송 경로로부터 몰을 제거하는 것을 더 포함하는 패킷 역추적 방법.
9. 제1항에 있어서, 회송 경로에 복수의 결탁 몰을 배치하는 것을 더 포함하는 패킷 역추적 방법.
10. 컴퓨터 판독가능 프로그램을 포함한 컴퓨터 사용가능 매체를 포함한 네트워크에서 패킷을 역추적하기 위한 컴퓨터 프로그램 제품에 있어서,

    컴퓨터 판독가능 프로그램은, 컴퓨터에서 실행될 때, 컴퓨터로 하여금,

    네트워크 내의 각 노드의 아이덴티티 번호(ID)를 유지하는 것과;

    각 회송 노드에서 이 노드와 싱크 사이에 공유된 비밀키를 이용하여 서명을 발생시키는 것과;

    싱크에서 패킷을 수신한 때, 각 패킷의 서명의 정확함을 서명이 추가된 순서의 역순으로 싱크에 의해 검증하는 것과;

    회송 경로의 서명 유효성을 결정하여 오류 데이터 주입 소스를 결정하는 것

    을 수행하게 하는 것인 컴퓨터 프로그램 제품.

Images