경로 탐색

경로 탐색은 분야에 따라 서로 다른 두 일을 가리키는 이름입니다. 게임과 지도에서는 출발점에서 목적지까지 갈 길을 계산해 내는 일을 말합니다. 보안에서는 파일 이름에 위 폴더로 올라가는 표시를 섞어 서버가 열면 안 되는 파일을 열게 만드는 공격을 말합니다. 앞의 뜻은 일부러 만드는 기능입니다. 뒤의 뜻은 막아야 할 구멍입니다.

상세

이 절은 두 뜻을 표로 가른 뒤 길을 찾는 계산과 폴더를 거슬러 오르는 공격을 차례로 봅니다. 끝에는 문서에서 만난 경로 탐색이 어느 뜻인지 가르는 단서를 둡니다.

두 맥락과 두 뜻

두 뜻은 방향이 반대입니다. 첫째 뜻은 개발자가 일부러 만들어 넣는 기능입니다. 둘째 뜻은 개발자가 빠뜨린 검사를 공격자가 파고드는 결함입니다.

영어에서는 두 이름이 다릅니다. 우리말로 옮길 때 둘 다 「경로 탐색」이라 부르는 일이 있어 뜻이 겹칩니다. 보안 쪽 뜻은 「경로 순회」나 「디렉터리 트래버설」로도 부릅니다.

길을 찾는 계산

게임 속 NPC(Non-Player Character, 사람이 조종하지 않는 캐릭터)가 플레이어를 쫓는 장면을 떠올려 봅니다. 둘 사이에 벽이 있으면 플레이어 쪽으로 곧장 걷기만 해서는 벽에 막힙니다. NPC 는 벽을 돌아가는 길을 미리 알아야 합니다. 이 길을 계산하는 일이 첫째 뜻의 경로 탐색입니다.

컴퓨터는 그림으로 된 지도를 바로 다루지 못하므로 먼저 지도를 그래프로 바꿉니다. 그래프는 점과 그 점들을 잇는 선으로 이루어진 구조입니다. 점을 노드, 선을 간선이라고 부릅니다.

지도에 맞추면 지나갈 수 있는 곳을 노드로, 한 번에 옮겨 갈 수 있는 사이를 간선으로 삼습니다.

지도를 노드로 나누는 방법은 대개 둘입니다. 하나는 바닥을 바둑판처럼 같은 크기의 칸으로 자르는 격자입니다. 칸 하나가 노드입니다. 맞닿은 칸끼리 간선으로 잇습니다.

다른 하나는 걸을 수 있는 바닥만 다각형 여러 개로 덮는 내비게이션 메시입니다. 다각형 하나가 노드입니다. 넓은 방바닥도 다각형 몇 개면 덮이므로 칸으로 자를 때보다 노드가 훨씬 적습니다.

간선마다 지나가는 비용을 붙입니다. 비용은 대개 거리입니다. 늪이나 비탈처럼 걷기 힘든 곳은 거리가 같아도 비용을 더 크게 매깁니다.

그래서 경로 탐색이 찾는 길은 가장 짧은 길이 아니라 지나온 간선의 비용을 모두 더한 값이 가장 작은 길입니다. 출발점부터 어떤 노드까지 이렇게 더한 값을 그 노드의 쌓인 비용이라고 부릅니다.

탐색은 출발 노드에서 시작해 바깥으로 넓혀 갑니다. 다음에 살펴볼 노드들을 후보 목록에 모아 둡니다. 그중 가장 유망한 것을 하나씩 꺼내 이웃을 살핍니다. 무엇을 유망하다고 볼지는 아래 표에서 가릅니다.

이웃을 후보 목록에 넣을 때는 그 이웃이 어느 노드에서 왔는지도 함께 적어 둡니다. 목적지를 꺼내는 순간 탐색이 끝납니다. 그때 적어 둔 기록을 목적지부터 거꾸로 따라가면 출발점까지 이어진 길이 나옵니다.

flowchart TD
    A["출발 노드를 후보 목록에 넣는다"] --> B["후보 중 가장 유망한 노드를 꺼낸다"]
    B --> C{"목적지인가"}
    C -->|예| D["거쳐 온 노드를 거꾸로 이어 길을 만든다"]
    C -->|아니오| E["이웃 노드까지 쌓인 비용을 계산해 후보 목록에 넣는다"]
    E --> B

그림에서 「가장 유망한」을 무엇으로 정하느냐에 따라 이름 붙은 방법이 갈립니다. 아래 표는 그중 셋입니다.

A* 가 쓰는 어림값을 휴리스틱이라고 부릅니다. 장애물을 무시하고 목적지까지 곧게 잰 거리를 어림값으로 쓸 수 있습니다. 어림값이 실제 남은 비용보다 크지 않으면 A* 도 가장 싼 길을 찾아냅니다.

게임에는 시간 제약이 하나 붙습니다. 게임은 화면을 1초에 수십 번 다시 그립니다. 한 번 그리는 단위를 프레임이라고 합니다. 경로 탐색이 한 프레임에 주어진 시간을 넘기면 화면이 멈칫거립니다. 그래서 캐릭터 여럿의 탐색을 여러 프레임에 나눠 돌리거나, 자주 쓰는 길을 미리 계산해 둡니다.

장애물이 없는 빈 들판이라면 목적지 쪽으로 곧장 움직이면 되므로 경로 탐색이 필요 없습니다. 벽이나 막힌 길 때문에 곧은 길이 통하지 않을 때 씁니다. 길을 찾은 뒤 움직이는 동안 다른 캐릭터와 부딪히지 않게 비켜 가는 일은 회피가 따로 맡습니다.

폴더를 거슬러 오르는 공격

둘째 뜻을 보려면 파일 경로부터 알아야 합니다. 파일 시스템은 파일을 폴더 안에 넣고, 폴더를 다시 더 큰 폴더 안에 넣는 나무 모양으로 정리합니다. 맨 위 폴더를 루트라고 부릅니다. 리눅스에서는 루트를 / 로 적습니다. 루트에서 파일까지 내려가는 폴더 이름을 / 로 이어 적은 글줄이 경로입니다.

경로에는 특별한 이름이 하나 있습니다. .. 은 「한 단계 위 폴더」를 뜻합니다. /srv/files/../etc 는 files 에서 한 단계 올라간 /srv 아래의 etc 입니다.

경로 안의 .. 을 풀어 같은 곳을 가리키는 가장 짧은 꼴로 바꾸는 일을 경로 정규화라고 합니다. 앞의 /srv/files/../etc 를 정규화하면 /srv/etc 가 됩니다. 정규화해야 경로가 실제로 어느 폴더를 가리키는지 한눈에 보입니다.

파일 내려받기 기능을 예로 듭니다. 서버는 /srv/files 폴더에 올려 둔 문서를 내줍니다. 요청은 /download?name=report.pdf 꼴입니다. 서버 코드는 기준 폴더 뒤에 name 값을 붙여 파일을 엽니다. 개발자는 name 에 문서 이름만 올 것이라 믿습니다.

공격자는 name 에 ../../etc/passwd 를 넣습니다. 서버가 붙인 경로는 /srv/files/../../etc/passwd 가 됩니다. 운영체제는 .. 두 번을 따라 files 와 srv 를 거슬러 올라 루트에 닿습니다. 거기서 /etc/passwd 를 엽니다. 이 파일은 리눅스가 계정 목록을 적어 두는 파일입니다.

flowchart TD
    R["/ · 루트"] --> ETC["etc"]
    R --> SRV["srv"]
    ETC --> P["passwd · 계정 목록"]
    SRV --> F["files · 기준 폴더"]
    F --> D["report.pdf"]
    F -.->|"../ 한 번"| SRV
    SRV -.->|"../ 한 번 더"| R

그림의 점선이 공격자가 넣은 .. 두 번입니다. 기준 폴더에서 두 번 올라가면 루트입니다. 거기서 etc 로 내려가면 원래는 닿을 수 없던 파일입니다.

피해는 어느 파일에 닿느냐에 달렸습니다. 설정 파일에는 데이터베이스 비밀번호 같은 비밀 값이 들어 있기도 합니다. 업로드 기능에서 같은 실수를 하면 공격자가 기준 폴더 밖에 파일을 써 넣습니다. 서버가 실행하는 파일을 덮어쓰면 공격자의 코드가 그 서버에서 돕니다.

이 결함은 소프트웨어 약점 유형마다 번호를 붙인 목록인 CWE(Common Weakness Enumeration, 공통 약점 목록)에서 22번입니다. 검사 도구가 CWE-22 를 보고하면 이 뜻의 경로 탐색을 찾았다는 말입니다.

기준 폴더 밖으로 나가는지 확인하기

막는 방법의 뼈대는 하나입니다. 입력을 기준 폴더에 붙여 경로를 만듭니다. 그 경로를 정규화해서 .. 을 모두 풉니다. 그 결과가 아직 기준 폴더 안에 있을 때만 파일을 엽니다. 아래는 자바로 이 확인을 하는 모습입니다.

Path base = Path.of("/srv/files");

Path bad = base.resolve("../../etc/passwd")
               .normalize();
bad.toString();       // "/etc/passwd"
bad.startsWith(base); // false

Path ok = base.resolve("a/../b.txt")
              .normalize();
ok.toString();        // "/srv/files/b.txt"
ok.startsWith(base);  // true

resolve 는 기준 폴더 뒤에 입력을 붙입니다. normalize 는 .. 을 풉니다. 첫째 입력은 풀고 나니 기준 폴더 밖이라 startsWith 가 false 를 돌려줍니다. 서버는 이때 요청을 거절합니다. 둘째 입력도 .. 을 품었지만 풀린 결과가 기준 폴더 안이라 통과합니다.

이 뼈대를 줄여서 흉내 내면 구멍이 납니다. 아래 표에 나오는 낱말 둘을 먼저 풉니다.

심볼릭 링크는 다른 위치의 파일을 가리키는 바로가기 파일입니다. 링크를 열면 운영체제가 가리키는 파일을 대신 엽니다.

URL 인코딩은 URL(Uniform Resource Locator, 웹 주소)에 바로 못 쓰는 글자를 % 와 16진수 두 자리로 바꿔 적는 방식입니다. 점 . 은 %2e, 빗금 / 는 %2f 로 적힙니다.

첫 줄은 ..[../]/ → ../ 처럼 읽습니다. 가운데 ../ 가 지워지면 앞의 .. 과 뒤의 / 가 붙어 다시 ../ 가 됩니다.

마지막 줄까지 막으려면 링크를 끝까지 따라가 파일의 진짜 위치를 구한 뒤 기준 폴더와 견줍니다. 자바에서는 toRealPath 가 그 위치를 구해 줍니다.

가장 단단한 방법은 사용자에게 파일 이름을 받지 않는 것입니다. 파일마다 번호를 매겨 둡니다. 요청에는 번호만 받으면 경로를 만들 재료가 공격자 손에 들어가지 않습니다. 받을 수 있는 이름을 미리 정해 두는 허용 목록도 같은 생각입니다.

어느 뜻인지 가르는 단서

문서에서 경로 탐색을 만나면 함께 나오는 낱말을 봅니다. 대개 그것만으로 뜻이 갈립니다.

게임 엔진이나 알고리즘 책에서 나오면 첫째 뜻입니다. 보안 점검 보고서나 취약점 목록에서 나오면 둘째 뜻입니다.

관련 항목

길을 찾는 계산이 쓰는 탐색 방법

너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · A* 알고리즘 · 휴리스틱 · 최단 경로 문제 · 우선순위 큐

길을 찾는 계산이 다루는 지도 표현

그래프 · 노드 · 간선 · 가중치 그래프 · 격자 · 내비게이션 메시 · 웨이포인트

게임에서 경로 탐색과 함께 도는 장치

게임 개발 · 논플레이어 캐릭터 · 게임 AI · 회피 · 행동 트리 · 충돌 · 게임 루프 · 프레임

폴더를 거슬러 오르는 공격이 노리는 파일 경로 개념

파일 시스템 · 루트 디렉터리 · 절대 경로 · 상대 경로 · 경로 정규화 · 심볼릭 링크 · 작업 디렉터리

이 공격과 같은 입력 검증 실패에서 나오는 취약점

CWE · 취약점 · SQL 인젝션 · 명령 주입 · 교차 사이트 스크립팅 · 서버 사이드 요청 위조 · 파일 업로드 취약점 · 로컬 파일 포함

이 공격을 막는 수단

입력 검증 · 허용 목록 · URL 인코딩 · 샌드박스 · chroot · 최소 권한 원칙

경로 탐색과 이름이 겹치거나 닮은 표제어

경로 순회 · 디렉터리 트래버설 · 경로 조작 · 경로 MTU 탐색 · 라우팅