사이버 가디언

옛날 좋은 시절, 인터넷에는 두려움도 테러도 없었다. 사람들은 사이버 범죄자나 미친 컴퓨터 과학자를 걱정할 필요가 없었다. 하지만 오늘날, 연결을 끊고 있지 않는 한 어디에 있든 끔찍한 크래커와 마주친다. 그들의 공격으로부터 자신을 지켜야 한다.

뛰어난 소프트웨어 구축 능력과 강한 정의감을 가진 당신은 사이버 가디언으로 일하게 되었다. 궁극적인 임무는 네트워크에 침입하는 침입자를 완전히 차단하고 아이들을 인터넷의 유해 정보로부터 보호하는 완벽한 방화벽 시스템을 만드는 것이다. 그러나 이는 극히 어렵고 아무도 성공한 적이 없다. 대신 첫 단계로, 훨씬 단순한 가정 아래에서 동작하는 소프트웨어 시뮬레이터를 작성해야 한다.

일반적으로 방화벽 시스템은 조직(예: 회사나 대학교)의 로컬 네트워크 입구에서 동작하며 로컬 관리 정책을 시행한다. 인바운드와 아웃바운드 패킷(참고: 인터넷에서 전송되는 데이터는 패킷이라 불리는 작은 조각으로 나뉜다)을 모두 받아 각각이 적법한지 하나씩 검사한다. 적법성의 정의는 사이트마다 다를 수 있고 조직의 로컬 관리 정책에 따라 달라질 수 있다. 당신의 시뮬레이터는 수신 패킷뿐 아니라 로컬 관리 정책을 나타내는 데이터도 받아들여야 한다.

이 문제에서는 단순화를 위해 각 네트워크 패킷이 출발지 주소, 목적지 주소, 메시지 본문의 세 필드로 이루어진다고 가정한다. 출발지 주소는 패킷을 전송하는 컴퓨터나 기기를 지정하고, 목적지 주소는 패킷이 전송되는 컴퓨터나 기기를 지정한다. 이 시뮬레이터에서 주소는 192.168.1.1 같은 표준 IP 주소 표기 대신 03214567이나 31415926 같은 여덟 자리로 표현된다. 관리 정책은 필터링 규칙으로 기술되며, 각 규칙은 출발지-목적지 주소 쌍의 어떤 집합을 지정하고 그 주소 쌍을 가진 패킷을 적법 또는 부적법으로 정의한다.

입력은 여러 데이터 세트로 이루어지며, 각 데이터 세트는 다음 형식으로 필터링 규칙과 수신 패킷을 나타낸다:

n m
rule1
rule2
...
rulen
packet1
packet2
...
packetm

첫 줄은 두 음이 아닌 정수 n과 m으로 이루어진다. n과 m이 모두 0이면 입력의 끝을 뜻한다. 그렇지 않으면 각각 필터링 규칙을 나타내는 n개의 줄과 각각 도착하는 패킷을 나타내는 m개의 줄이 이 순서대로 뒤따른다. n과 m은 1,024 이하라고 가정할 수 있다.

각 rulei는 다음 형식 중 하나이다:

• permit source-pattern destination-pattern
• deny source-pattern destination-pattern

source-pattern 또는 destination-pattern은 길이 8의 문자열이며, 각 문자는 숫자('0'부터 '9') 또는 와일드카드 문자 '?' 중 하나이다. 예를 들어 "1????5??"는 첫 번째와 다섯 번째 자리가 각각 '1'과 '5'인 모든 주소와 일치한다. 일반적으로 와일드카드 문자는 임의의 한 숫자와 일치하고, 숫자는 자기 자신과만 일치한다.

키워드 "permit"과 "deny"로 필터링 규칙은 각각 적법한 패킷과 부적법한 패킷을 지정한다. 즉, 패킷의 출발지 주소와 목적지 주소가 각각 source-pattern과 destination-pattern에 일치하면, 키워드에 따라 방화벽을 통과하도록 허가되거나 요청이 거부된다. permit 규칙과 deny 규칙은 같은 출발지-목적지 주소 쌍을 공유할 수 있으므로 모순될 수 있다. 충돌 해결을 위해 우선순위 규칙을 정의한다: rulei는 i > j일 때 그리고 그때만 rulej보다 우선순위가 높다. 완전성을 위해 기본 규칙을 정의한다: 주어진 규칙 중 어느 것도 명시적으로 적법하다고 지정하지 않은 패킷은 부적법하다.

패킷은 다음 형식이다:

• source-address destination-address message-body

처음 두 개는 각각 숫자로만 이루어진 길이 8의 문자열이다. 마지막은 영숫자('a'부터 'z', 'A'부터 'Z', '0'부터 '9')로만 이루어진 문자열이다. 메시지 본문에는 공백이나 특수 문자도 나타날 수 없다. 비어 있지 않고 길이가 50 이하라고 가정할 수 있다.

규칙이나 패킷을 나타내는 입력 줄에서 인접한 두 필드 사이에는 정확히 하나의 공백 문자가 있다고 가정할 수 있다.

각 데이터 세트마다 첫 줄에 적법한 패킷의 개수를 출력하고, 이어서 데이터 세트에 나타난 순서대로 모든 적법한 패킷을 출력한다. 각 패킷은 정확히 한 줄에 쓰여야 한다. 데이터 세트에 출발지 주소, 목적지 주소, 메시지 본문이 같은 패킷이 두 개 있으면 서로 다른 패킷으로 간주하여 서로 다른 줄에 써야 한다. 여분의 공백이나 여분의 빈 줄을 출력해서는 안 된다.