저작권 안내: 저작권자표시 Yes 상업적이용 No 컨텐츠변경 No

스프링5 입문

JSP 2.3

JPA 입문

DDD Start

인프런 객체 지향 입문 강의

ip-filter 구현 이야기 발표 자료:



관련 글:





Posted by 최범균 madvirus

댓글을 달아 주세요

ip-filter-core 모듈은 아래와 같이 Config 객체를 이용해서 차단/허용 목록을 설정한다. (ip-filter의 사용법은 https://github.com/madvirus/ip-filter/wiki/HOME_kr 문서를 참고하기 바란다.)


Config config = new Config();

config.setAllowFirst(true);

config.setDefaultAllow(false);

config.allow("1.2.3.4"); // 허용 IP 추가

config.allow("10.20.30.40");

config.deny("101.102.103.104"); // 차단 IP 추가


IpFilter ipFilter = IpFilters.create(config);


ipFilter.accept("1.2.3.4"); // true

ipFilter.accept("101.102.103.104"); // false


코드로 설정하는 것이 필요할 때가 있지만, 아래와 같은 문자열을 이용할 수 있다면 파일이나 운영툴 등에서 쉽게 설정할 수 있을 것이다.


# 주석

order allow,deny

default true

allow from 1.2.3.4

allow from 1.2.5.* # 뒤에 주석

allow from 201.202.203.10/64

deny from all


위 문자열을 읽어와서 Config 객체를 생성하려면 문자열을 알맞게 파싱해 주어야 하는데, 파싱을 어떻게 할까 고민하다가 최근에 학습하고 있는 스카라(Scala)의 콤비네이터 파서(Conbinator parser)를 사용해 보기로 했다. 스카라는 자체적으로 Context-free grammer 에 따른 파싱 기능을 제공하고 있기 때문에, ANTLR과 같은 별도의 파서 생성기를 사용하지 않아도 된다.


스카라를 이용한 문자열 파서


음,, 먼저 스카라에 익숙하지 않은 분들은 아래 코드가 잘 이해되지 않을 것이다. 그래도 그냥 읽어보기 바란다. 설정 문자열을 파싱하기 위해 작성한 스카라 코드는 아래와 같다. (아래 코드는 order나 default를 여러 줄 입력해도 에러를 발생시키진 않는데, order나 default를 여러번 설정할 경우 오류를 발생시킬지의 여부는 고민 중에 있다.)


class Conf extends JavaTokenParsers {

  override val whiteSpace = """[ \t]+""".r


  def conf: Parser[Config] = repsep(confPart, eol) ^^ (

    x => {

      val config = new Config

      x.foreach(part =>

        part match {

          case ("order", firstAllow: Boolean) => config.setAllowFirst(firstAllow)

          case ("default", defaultAllow: Boolean) => config.setDefaultAllow(defaultAllow)

          case ("allow", ip: String) => config.allow(ip)

          case ("deny", ip: String) => config.deny(ip)

          case _ =>

        })

      config

    }

    )


  def confPart: Parser[Any] = commentPart | orderPart | defaultPart | allowOrDenyPart | emptyLine


  def commentPart: Parser[String] = """#(.*)""".r ^^ (x => x)


  def orderPart: Parser[Tuple2[String, Boolean]] =

    "order" ~ orderValue ~ opt(commentPart) ^^ (x => ("order", x._1._2))


  def orderValue: Parser[Boolean] = {

    "allow" ~ "," ~ "deny" ^^ (x => true) |

      "deny" ~ "," ~ "allow" ^^ (x => false)

  }


  def defaultPart: Parser[Tuple2[String, Boolean]] = 

      "default" ~ booleanValue ^^ (x => ("default", x._2))


  def booleanValue: Parser[Boolean] = "true" ^^ (x => true) | "false" ^^ (x => false)


  def allowOrDenyPart: Parser[Tuple2[String, String]] =

    allow ^^ (x => ("allow", x)) | deny ^^ (x => ("deny", x))


  def allow: Parser[String] = "allow" ~ "from" ~ ipPattern ~ opt(commentPart) ^^ (x => x._1._2)


  def deny: Parser[String] = "deny" ~ "from" ~ ipPattern ~ opt(commentPart) ^^ (x => x._1._2)


  def ipPattern: Parser[String] =

    "all" ^^ (x => "*") |

      """(\d+\.){1,3}(\*)""".r ^^ (x => x) |

      """(\d+\.\d+\.\d+\.\d+\/\d+)""".r ^^ (x => x) |

      """(\d+\.\d+\.\d+\.\d+)""".r ^^ (x => x)


  def emptyLine: Parser[String] = ""


  def eol: Parser[String] = """(\r?\n)+""".r

}


class ConfParser extends Conf {

  def parse(confText: String): Config = {

    val result = parseAll(conf, confText)

    if (result.successful)

      result.get

    else

      throw new ConfParserException(result.toString)

  }

}


Conf 클래스는 문자열을 파싱해서 Config 객체를 생성해주는 기능을 제공하며, ConfParser 클래스는 외부에 파싱 기능을 제공하는 parse() 메서드를 제공한다.


자바 코드에서는 ConfParser 클래스를 이용해서 문자열로부터 Config 객체를 생성할 수 있다.


public class UsingConfParserTestInJava {

    @Test

    public void useConfParser() {

        String confValue =

                "order deny,allow\n" +

                        "allow from 1.2.3.4\n" +

                        "deny from 10.20.30.40\n" +

                        "allow from 101.102.103.*\n" +

                        "allow from 201.202.203.10/64";


        Config config = new ConfParser().parse(confValue);

        assertFalse(config.isAllowFirst());

        assertEquals(config.getAllowList().size(), 3);

    }


응용


문자열로부터 Config 객체를 생성하는 파서를 만들었으니, 이제 파일이나 다른 곳에서 설정 데이터를 읽어와 Config 객체를 만들 수 있게 되었다. 실제 응용은 웹 어플리케이션에서 특정 IP 차단을 위해 작성한 ip-filter-web-simple 에서 사용하였다. (관련 코드는 https://github.com/madvirus/ip-filter/tree/master/ip-filter-web-simple 에서 확인 가능)


package org.chimi.ipfilter.web.impl;


import org.chimi.ipfilter.Config;

import org.chimi.ipfilter.parser.ConfParser;


import java.io.FileReader;

import java.io.IOException;


public class FileConfigFactory extends ConfigFactory {


    @Override

    public Config create(String value) {

        return new ConfParser().parse(readFromFile(value));

    }


    private String readFromFile(String fileName) {

        try {

            return IOUtil.read(new FileReader(fileName));

        } catch (IOException e) {

            throw new ConfigFactoryException(e);

        }

    }


    @Override

    public boolean isReloadSupported() {

        return true;

    }


}



Posted by 최범균 madvirus

댓글을 달아 주세요

지난 글 "IP 필터 만들기 1, 아이디어"에서 트리 구조로 허용/차단 IP 목록을 표시하는 방법을 정리해봤는데, 이번 글에서는 실제 구현을 살펴보도록 하겠다. 참고로, 본 글에서 설명하는 모든 코드는 https://github.com/madvirus/ip-filter 에 공개되어 있으니 참고하기 바란다.


IP 트리 구성을 위한 클래스: IpTree, NumberNode


ip-filter 모듈에서 사용하는 IP 목록은 아래와 같은 방식으로 표현한다.


1.2.3.4

1.2.3.64/26

5.6.7.*

10.20.*

30.*


이를 트리로 표현하기 위해 두 개의 클래스를 작성하였다.

  • IpTree: 트리의 관리 및 특정 IP가 트리로 표현되는지 확인해주는 기능
  • NumberNode: 트리의 각 노드를 표현


NumberNode 구현

NumberNode는 트리의 루트 노드부터 말단 노드까지를 표현한다. 노드는 위 그림에서 보듯 세 가지 종류의 값을 갖는다.
  • 숫자
  • 별표(*)
  • 네트워크주소표현 (예, 128/25)
이를 표현하기 위해 NumberNode 객체의 생성 부분을 아래와 같이 구현하였다.

public class NumberNode {

    private final String number;

    private boolean isSimpleNumber;
    private int filterNumber;
    private int lastValueOfNetworkNumber;
    private boolean allAccept;

    public NumberNode(String number) {
        this.number = number;
        processPattern();
    }

    private static int[] filterNumbers = {
            0x00, // 24
            0x80, // 25
            0xC0, // 26
            0xE0, // 27
            0xF0, // 28
            0xF8, // 29
            0xFC // 30
    };

    private void processPattern() {
        if (number.equals("*")) {
            isSimpleNumber = false;
            allAccept = true;
            return;
        }
        int slashIdx = number.indexOf("/");
        if (slashIdx == -1) {
            isSimpleNumber = true;
            return;
        }
        // 64/26과 같은 네트워크 주소 형식 처리 위한 코드
        this.lastValueOfNetworkNumber = Integer.parseInt(number.substring(0, slashIdx));
        int bitsOfNetworkNumber = Integer.parseInt(number.substring(slashIdx + 1));

        this.filterNumber = filterNumbers[bitsOfNetworkNumber - 24];
        this.isSimpleNumber = false;
    }

위 코드에서 각 필드는 다음과 같다.
  • isSimpleNumber: 값이 숫자면 true, 별표나 네트워크주소 표현이면 false
  • allAccept: 값이 별표면 true, 아니면 false
  • 네트워크 주소 관련 필드 (값 형식이 A/B 인 경우)
    • lastValueOfNetworkNumber: A/B 형식에서 A 값. 예, 128/25 에서 128
    • filterNumber: 데이터 비교시에 사용할 숫자 (뒤에서 설명)
값 일치 여부 확인

NumberNode를 생성한 뒤에, 해당 노드가 특정 숫자와 매칭되는지 여부를 확인하는 기능이 필요하다. 이를 위해 isMatch() 메서드를 아래와 같이 구현하였다.

public class NumberNode {

    private final String number;

    private boolean isSimpleNumber;
    private int filterNumber;
    private int lastValueOfNetworkNumber;
    private boolean allAccept;

    public boolean isMatch(String number) {
        if (allAccept) return true; // this.number가 "*" 인 경우
        if (isSimpleNumber) return this.number.equals(number); // this.number가 숫자인 경우

        // this.number가 A/B 형식인 경우
        int filtered = filterNumber & Integer.parseInt(number);
        return filtered == lastValueOfNetworkNumber;
    }

위 코드는 아래와 같이 작동한다.

NumberNode n1 = new NumberNode("128");
n1.isMatch("10"); // false
n1.isMatch("128"); // true

NumberNode n2 = new NumberNode("*");
n2.isMatch("0"); // true
n2.isMatch("123"); // true

NumberNode n3 = new NumberNode("128/25");
n3.isMatch("128"); // true
n3.isMatch("200"); // true
n3.isMatch("255"); // true
n3.isMatch("127"); // false
n3.isMatch("100"); // false

[박스] 네트워크 주소
"64/26"에 대해 약간의 설명이 필요할 것 같다. 흔히 네트워크 주소라 하면, 아래와 같이 표시한다.

2.4.8.64/26

여기서 숫자들은 각각 한 바이트를 차지하며, 여기서 마지막 64/26은 네트워크 범위를 지정하는 숫자가 된다. 이 예의 경우 64는 네트워크 범위 기준점이 되는 네 번째 바이트의 값이며, 26은 전체 주소에서 네트워크 주소로 사용될 비트 길이가 된다. 위 숫자에서 2.4.8.64는 아래와 같이 비트로 표현할 수 있는데,

00000010 00000100 00001000 01000000 (2 4 8 64)

여기서 앞에서 26개 비트, 즉 아래 값이 2.4.8.64/26 네트워크에서 사용할 네트워크 주소가 된다.

00000010 00000100 00001000 01 (앞에서부터 26비트)

이 네트워크 주소에서 사용할 수 있는 주소 범위는 아래와 같다.

00000010 00000100 00001000 01000000 ~ 
00000010 00000100 00001000 01111111

즉, 마지막 주소로 64 부터 127 까지가 64/26에 해당하는 숫자 범위이다. 따라서, 어떤 주소가 이 네트워크 주소 범위에 포함되는 확인하려면 다음과 같이 64/26에 해당하는 비교 값과 실제 주소 값을 AND 연산해서 네트워크 주소값이 나오는지 확인해보면 된다.

11111111 11111111 11111111 11000000 (필터 위한 비교 값)
00000010 00000100 00001000 01001100 (실제 주소)
---------------------------------- (AND 연산)
00000010 00000100 00001000 01000000 -> 네트워크 주소 값과 일치하므로, 이 주소는 네트워크 범위에 포함

앞서 NumberNode는 이 방식을 사용해서 특정 숫자가 범위에 포함되는 지 확인한다.

자식 노드 생성을 위한 메서드

NumberNode는 자식 노드를 생성/보관/검색하는 기능을 제공함으로써, 뒤에서 설명할 IpTree가 내부적으로 노드를 쉽게 구성할 수 있도록 하였다. 이와 관련된 코드는 아래와 같다.

public class NumberNode {
    ...
    private Map<String, NumberNode> simpleChildNodeMap = new HashMap<String, NumberNode>();
    private List<NumberNode> patternChildNodes = new ArrayList<NumberNode>();

    public NumberNode createOrGetChildNumber(String numberPattern) {
        if (simpleChildNodeMap.containsKey(numberPattern))
            return simpleChildNodeMap.get(numberPattern);

        for (NumberNode patternChild : patternChildNodes)
            if (patternChild.number.equals(numberPattern))
                return patternChild;

        NumberNode childNode = new NumberNode(numberPattern);
        if (childNode.isSimpleNumber)
            simpleChildNodeMap.put(number, childNode);
        else
            patternChildNodes.add(childNode);

        return childNode;
    }

    public NumberNode findMatchingChild(String number) {
        NumberNode simpleChildNode = simpleChildNodeMap.get(number);
        if (simpleChildNode != null) return simpleChildNode;

        for (NumberNode patternChildNode : patternChildNodes)
            if (patternChildNode.isMatch(number))
                return patternChildNode;

        return null;
    }
    ...
}

createOrGetChildNumber() 메서드는 NumberNode는 자식 노드를 두 가지 방식으로 보관한다.
  • 정확한 숫자는 simpleChildNodeMap 에 <숫자값, 자식노드>로 보관 (숫자값이 키)
  • A/B 형식의 패턴 및 "*"은 patternChildNodes 에 추가
createOrGetChildNumber() 메서드는 동일한 숫자를 가진 자식 노드가 존재하면 그 노드를 리턴하고, 존재하지 않으면 새로 생성해서 자식 노드로 추가한다. 이 메서드는 IpTree 클래스가 IP 문자열로부터 트리 노드를 생성할 때 사용된다.

findMatchingChild() 메서드는 입력받은 숫자와 매칭되는 자식 노드를 구해서 리턴해준다. 이 메서드는 IpTree에서 특정 IP 문자열이 트리에 매칭되는 지 확인하기 위해 사용된다.

IpTree 구현

IpTree 클래스는 다음의 두 기능을 제공한다.

  • IP 문자열을 트리로 구성해주는 기능을 제공한다. 
  • 특정 IP 문자열이 트리에 매칭되는지 확인하는 기능을 제공한다.
실제 구현은 아래와 같다.

public class IpTree {
    private NumberNode root = new NumberNode("");

    public void add(String ip) {
        String[] ipNumbers = ip.split("\\.");
        NumberNode node = root;
        for (String number : ipNumbers) {
            node = node.createOrGetChildNumber(number);
        }
    }

    public boolean containsIp(String ip) {
        String[] ipNumbers = ip.split("\\.");
        NumberNode node = root;
        for (String number : ipNumbers) {
            node = node.findChildNumber(number);
            if (node == null)
                return false;
            if (node.isAllAccept())
                return true;
        }
        return true;
    }
}


IpTree 클래스는 아래와 같이 사용한다.


IpTree tree = new IpTree();

tree.add("1.2.3.4");

tree.add("1.2.4.5");

tree.add("1.2.5.*");

tree.add("1.2.6.128/25");


tree.containsIp("1.2.3.4"); // true

tree.containsIp("1.2.3.5"); // false

tree.containsIp("1.2.6.129"); // true

tree.containsIp("1.2.5.4"); // true


실제 IP Filter 기능 구현


IP 필터는 다음과 같이 두 개의 IP 목록을 갖는다.

  • 허용 IP 목록
  • 차단 IP 목록
IP 필터는 이 두 개의 IP 목록을 별도의 IpTree 타입 필드를 이용해서 보관한다. 실제 IpFilter의 구현은 다음과 같다.

public class ConfigIpFilter implements IpFilter {

    private boolean defaultAllow;
    private IpTree allowIpTree;
    private IpTree denyIpTree;
    private boolean allowFirst;

    public ConfigIpFilter(Config config) {
        defaultAllow = config.isDefaultAllow();
        allowFirst = config.isAllowFirst();
        allowIpTree = makeIpTree(config.getAllowList());
        denyIpTree = makeIpTree(config.getDenyList());
    }

    private IpTree makeIpTree(List<String> ipList) {
        IpTree ipTree = new IpTree();
        for (String ip : ipList)
            ipTree.add(ip);
        return ipTree;
    }

    @Override
    public boolean accept(String ip) {
        if (allowFirst) {
            if (allowIpTree.containsIp(ip)) return true;
            if (denyIpTree.containsIp(ip)) return false;
        } else {
            if (denyIpTree.containsIp(ip)) return false;
            if (allowIpTree.containsIp(ip)) return true;
        }
        return defaultAllow;
    }

}

ConfigIpFilter는 Config로부터 허용 IP 목록과 차단 IP 목록을 읽어와 각각을 위한 IpTree를 생성한다. accept() 메서드는 이 IpTree 객체를 이용해서 지정한 IP가 차단 IP인지, 허용 IP인지 여부를 결정한다. 참고로, ConfigIpFilter 클래스의 사용법은 아래와 같다.

    @Test
    public void shouldReturnTrueToAllowedIpAndReturnFalseToDeniedIp() {
        Config config = new Config();
        config.setDefaultAllow(true);
        config.setAllowFirst(true);
        config.allow("1.2.3.4");
        config.allow("1.2.3.5");
        config.allow("1.2.3.64/26"); // // 01xxxxxx 범위 : 64~127
        config.deny("5.6.7.8");
        config.deny("101.102.103.32/27"); // 001xxxxx 범위: 32~63")

        IpFilter ipFilter = new ConfigIpFilter(config);
        assertTrue(ipFilter.accept("1.2.3.4"));
        assertTrue(ipFilter.accept("1.2.3.5"));
        assertTrue(ipFilter.accept("1.2.3.64"));
        assertTrue(ipFilter.accept("1.2.3.65"));
        assertTrue(ipFilter.accept("1.2.3.127"));
    }


성능 확인


ConfigIpFilter의 IP 필터 기능의 성능을 측정해 보았다. 이를 위해 다음의 IP 설정 목록을 차단 목록으로 추가하였다. 이 목록은 37,538 개 이며, 전체 목록은 https://github.com/madvirus/ip-filter/wiki/ip-list-config-for-performance-test 에서 확인할 수 있다.


1.0.1.*

1.0.2.*

1.0.3.*

...

101.253.*  
101.254.*  
103.1.8.*  
...
106.187.34.17
106.187.34.18
106.187.34.19
...
223.223.207.*
223.240.*
223.241.*
...
223.255.252.*
223.255.253.*


이 IP 설정이 포함하는 IP 개수는 약 3억 3천만이다. 


테스트는 아래와 같이 진행하였다.

  • 테스트 과정
    • 위 IP 설정 목록을 이용해서 차단 IP 목록으로 사용하는 IpFilter 객체 생성
    • 테스트 IP 범위 목록 중 랜덤하게 5개의 패턴을 뽑아, 그 패턴에 해당하는 IP 들을 차례대로 테스트 진행
      • 5개의 패턴이 적어 보일 수 있으나, 36.16.0.0~36.37.255.255 범위는 약 144만 개의 IP를 테스트
    • 각 IP를 검사하는 시간을 누적해서 평균 값 구함
  • 이 테스트를 5회 진행
비교 테스트를 위해 두 개의 IpFilter에 대해 테스트를 진행하였다..
  • 트리 기반으로 IP 목록을 유지하는 ConfigIpFilter 클래스
  • List를 이용해서 IP 목록을 유지하는 테스트용 ListIpFilter 클래스 (비교 목적으로 작성)
    • IP 확인 요청이 왔을 때, 허용IP/차단IP 목록을 순차적으로 비교 확인
두 번째 방식의 테스트는 안 하려고 했으나, 비교 자료를 원하시는 분들이 있을 것이기에 넣었다.


성능 비교 결과


테스트는 노트북에 진행했으면 노트북의 사양은 아래와 같다.

  • Intel Core i5-2457M @ 1.6 GHz
  • Windows 7 64bit 
  • JDK 6 (1.6.0_26)

성능 비교 결과 표를 아래와 같이 정리하였다.


[표1] 1개 쓰레드로 실행한 결과

-트리 방식


리스트 방식
회차

실행 회수

실행 시간 합
(밀리초)

실행 시간 평균
(밀리초)

실행 회수

실행 시간 합
(밀리초)

실행 시간 평균
(밀리초)

1

199,680

678

0.003400

50,944

28,631

0.562029

2

1,450,240

3,648

0.002516

1,212,928

181,893

0.152436

3

22,016

196

0.008931

12,800

6,397

0.499768

4

804,352

2,109

0.002622

377,088

152,709

0.404970

5

1,120,256

2,723

0.002431

273,920

14,964

0.054632

  

 평균

0.003980

 

평균 

0.334767


두 방식에서 확연한 속도 차이가 느껴진다. 트리 기반의 IP 필터 기능은 한 개 검사하는 데 0.004 밀리초(즉, 0.000004 초) 걸리는데 반해 리스트 방식은 0.335 밀리초로 (즉, 0.000335 초) 약 80배 이상 차이가 난다. 또한, 트리 방식은 실행 시간 평균이 균일한데 반해, 리스트 방식은 실행 시간 평균 10 배 이상 차이가 나기도 한다.


참고로, 트리 방식과 달리 리스트 방식이 이렇게 들쑥 날쑥한 이유는 리스트 방식이 풀스캔을 하기 때문이다. 트리 방식은 DB에 비교하면 인덱스를 사용해서 검색하는 방식이고, 리스트 방식은 인덱스 없이 전체 데이터를 스캔해서 검색하는 방식이다. 따라서, 리스트 방식에서 비교 대상이 앞쪽에 위치하면 검색 속도가 빠르고, 비교 대상이 뒤쪽에 위치하면 검색 속도가 그 만큼 느려지게 된다.


위와 동일한 테스트를 동시에 10개 쓰레드를 실행해서 테스트 해 보았다. 최대한 동시에 실행되는 효과를 만들기 위해 한 쓰레드가 최대 10만개의 IP만 검사하도록 제한을 걸었다. 테스트 결과는 아래와 같다.


[표2] 10개 쓰레드로 실행한 결과 (1쓰레드 당 최대 10만개까지만 검사)

-

트리 방식


리스트 방식
회차

실행 회수

실행 시간 합
(밀리초)

실행 시간 평균
(밀리초)

실행 회수

실행 시간 합
(밀리초)

실행 시간 평균
(밀리초)

1

695,840

7,592

0.010912

672,033

745,404

1.110667

2

816,640

6,325

0.007746

847,712

837,813

0.988323

3

698,304

6,301

0.009024

720,576

633,170

1.101748

4

901,120

8,216

0.009118

792,000

976,851

1.233398

5

664,096

5,576

0.008397

693,024

1,162,127

1.677894

 

 

 평균

0.009039

 

평균 

1.205352



1개 쓰레드를 이용한 경우와 10개 쓰레드를 이용한 경우를 비교해보면, 트리 방식에 비해 리스트 방식의 평균 실행 시간이 더 크게 증가한 것을 알 수 있다.


비교 목적으로 사용한 ListIpFilter 클래스 코드


트리 구조와 성능 비교 하기 위해 작성한 ListIpFilter의 코드는 아래와 같다.


public class ListIpFilter implements IpFilter {

    private boolean defaultAllow;

    private boolean allowFirst;

    private List<IpPattern> allowIpPatterns = new ArrayList<IpPattern>();

    private List<IpPattern> denyIpPatterns = new ArrayList<IpPattern>();


    public ListIpFilter(Config config) {

        defaultAllow = config.isDefaultAllow();

        allowFirst = config.isAllowFirst();

        for (String ipPattern : config.getAllowList())

            allowIpPatterns.add(new IpPattern(ipPattern));

        for (String ipPattern : config.getDenyList())

            denyIpPatterns.add(new IpPattern(ipPattern));

    }


    @Override

    public boolean accept(String ip) {

        if (allowFirst) {

            if (isAllowIp(ip)) return true;

            if (isDenyIp(ip)) return false;

        } else {

            if (isDenyIp(ip)) return false;

            if (isAllowIp(ip)) return true;

        }

        return defaultAllow;

    }


    private boolean isAllowIp(String ip) {

        for (IpPattern ipPattern : allowIpPatterns) {

            if (ipPattern.isMatch(ip))

                return true;

        }

        return false;

    }


    private boolean isDenyIp(String ip) {

        for (IpPattern ipPattern : denyIpPatterns) {

            if (ipPattern.isMatch(ip))

                return true;

        }

        return false;

    }


    private class IpPattern {


        private String exactMatchingPart;


        private boolean exactMatchingPattern = false;

        private boolean acceptAllPattern = false;

        private boolean rangePattern = false;


        private int fromNumberInRangePattern = 0;

        private int toNumberInRangePattern = 0;


        public IpPattern(String ipPattern) {

            if (ipPattern.endsWith("*")) {

                acceptAllPattern = true;

                exactMatchingPart = ipPattern.substring(0, ipPattern.length() - 1);

            } else {

                int slashIdx = ipPattern.indexOf("/");

                if (slashIdx == -1) {

                    exactMatchingPart = ipPattern;

                    exactMatchingPattern = true;

                } else {

                    int lastDotIdx = ipPattern.lastIndexOf(".");

                    exactMatchingPart = ipPattern.substring(0, lastDotIdx + 1);


                    int rangeNumber = Integer.parseInt(ipPattern.substring(lastDotIdx + 1, slashIdx));

                    int bitLength = Integer.parseInt(ipPattern.substring(slashIdx + 1));


                    rangePattern = true;

                    fromNumberInRangePattern = rangeNumber;

                    switch (bitLength) {

                        case 24:

                            toNumberInRangePattern = fromNumberInRangePattern + 0xFF;

                            break;

                        case 25:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x7F;

                            break;

                        case 26:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x3F;

                            break;

                        case 27:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x1F;

                            break;

                        case 28:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x0F;

                            break;

                        case 29:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x07;

                            break;

                        case 30:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x03;

                            break;

                    }

                }

            }

        }


        public boolean isMatch(String ip) {

            if (exactMatchingPattern)

                return ip.equals(exactMatchingPart);


            if (acceptAllPattern)

                return ip.startsWith(exactMatchingPart);


            if (rangePattern) {

                if (!ip.startsWith(exactMatchingPart)) return false;


                int lastNumberOfIp = Integer.parseInt(ip.substring(exactMatchingPart.length()));

                return lastNumberOfIp >= fromNumberInRangePattern 

                         && lastNumberOfIp <= toNumberInRangePattern;

            }

            return false;

        }

    }

}



참고 자료



Posted by 최범균 madvirus

댓글을 달아 주세요

  1. 2014.08.26 10:15  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

몇 년 전, 이전 직장에서 웹 게임의 CBT를 진행하는데, 갑자기 외부에서의 연결이 급격하게 느려지는 증상이 발생했다. 얼른 웹 서버와 DB에 들어가 봤으나 CPU/네트워크 관련 수치 모두 문제가 없었다. 내부에서의 연결은 문제 없이 잘 들어가졌다. 유관 팀과 함께 조사를 진행하다가 원인을 찾았다. 원인은 "방화벽의 차단 IP 목록"이었다.


방화벽에 등록된 차단 IP에 중국 IP 및 IP 대역들이 등록되어 있었는데, 그 개수가 많아서 트래픽 증가와 함께 방화벽의 CPU 사용률이 높아졌고 이로 인해 방화벽이 느려지는 문제가 발생했다. 웹 게임 서버로 들어오는 웹 요청을 방화벽이 빠르게 처리하지 못하자, 외부 게이머들의 불만이 폭주하기 시작했다. 일단, 방화벽의 IP 차단 목록의 개수를 줄여서 (정확하게는 화이트 리스트의 순위를 위로 올려서) 상황을 벗어났다. 그 당시 차단 IP 개수가 많아져도 성능이 저하되지 않는 IP 차단 모듈을 만들어봐야지라는 생각을 했고, 거의 3년이 지난 요즈음 IP 차단 기능을 제공하는 ip-filter 모듈 제작을 시작해서 0.1 버전을 만들었다.


아이디어


방화벽의 내부 구현을 알 순 없었지만, 검사할 IP 규칙 목록의 개수가 많았을 때 방화벽의 CPU 점유률이 높아지고 검사할 규칙 목록의 개수가 적었을 때 CPU 점유률이 낮아진 것으로 보아, 클라이언트의 IP에 해당하는 검사 규칙이 나타날 때 까지 순차적으로 각 규칙을 확인하는 것 같았다. 방화벽 설정에는 (중국 IP 대역 목록을 포함한) 매우 많은 차단 규칙이 앞쪽에 위치해 있었기 때문에, 클라이언트의 연결 요청이 들어오면 이 많은 차단 규칙을 다 확인한 뒤에 방화벽을 통과할 수 있는 것으로 추정되었다. IP가 규칙에 맞는지 여부를 확인하는 것은 순전히 CPU를 잡아 먹는 연산이기 때문에 동접자수가 증가할수록 CPU 점유률이 높아졌을 거라 생각된다.


그래서, 생각해본 것이 규칙 목록들을 트리 구조로 구성하는 것이었다. 예를 들어, 아래의 규칙에 해당하는 IP를 차단하고 싶다고 하자.

  • 1.2.3.4 (정확한 일치 IP)
  • 1.2.3.128/25 (1.2.3.128 ~ 1.2.3.255 대역)
  • 1.12.13.14 (정확한 일치 IP)
  • 10.20.* (10.20.0.0 ~ 10.20.255.255 대역)
  • 10.30.40.51 (정확한 일치 IP)
  • 10.30.40.52 (정확한 일치 IP)

이 검사 대상 IP 목록을 아래 그림과 같은 트리 형식으로 보관하는 것이다.



이렇게 트리 형식으로 검사할 규칙의 개수에 상관없이 항상 5 레벨 이하의 트리 탐색으로 특정 IP가 검사 규칙에 일치하는지 여부를 알아낼 수 있다. 예를 들어, IP 주소가 "1.12.13.5"라고 하자. 이 경우, 트리 상의 루트->1->12->13 까지는 일치하나 마지막 5레벨에서 IP 주소의 마지막 "5"와 일치하는 노드가 존재하지 않는다. 따라서, "1.12.13.5"는 매칭되는 규칙이 존재하지 않는다. 반면에 IP 주소가 "10.30.40.51"인 경우, 트리 상의 루트->10->30->40->51 에 정확하게 일치하므로, "10.30.40.51"은 매칭되는 규칙이 존재한다.


검사해야 할 규칙 목록이 백 개이든, 천 개이든, 만 개이든 상관없이 항상 5 레벨 이하의 트리 탐색으로 특정 IP가 검사 규칙에 걸리는지 확인할 수 있다. 따라서, 규칙 개수가 증가하더라도 앞서 순차적 검사와 달리 더 적은 CPU 시간을 사용할 거라 예상된다. 예를 들어, 규칙이 만 개이고 클라이언트 IP가 어떤 규칙에도 일치하지 않는다면, 만 번의 루프를 돈 뒤에야 비로서 클라이언트 IP가 규칙에 적용되지 않음을 알게 된다. 반면 위 트리 구조는 최대 5 레벨의 트리 탐색으로 클라이언트 IP가 규칙에 적용되는지 여부를 알 수 있다.


결과물


어떤 식으로 구현했는지 공유하기에 앞서 실제 만들어 본 0.1 버전을 github에 올려 보았다. 아래 github 사이트에서 ip-filter의 사용법과 소스를 확인해 볼 수 있다.

다음에는


다음에 정리해 볼 내용은 아래와 같은 것들이 있다.



Posted by 최범균 madvirus

댓글을 달아 주세요