RFC 7233 HTTP/1.1 Range フィールドの正規化

HTTP/1.1 オリジン・サーバで Range リクエストを扱えるように実装するには、 Range ヘッダを解釈しなければならないことはもちろんのこと、できれば重なっている範囲をまとめ、範囲の順番を昇順に並べておくと安全です。さらに範囲が複数指定されているときは、まとめた後の範囲の項目が多いときは範囲指定を不正扱いにするのが良いでしょう。これらを怠ると、攻撃に利用される危険性があります。

ということで、正規化した Ranges フィールド (RFC 7233 では canonical ranges と名づけています) を求める関数を書いてみます。

扱える範囲は bytes 限定とします。 関数 canonical_ranges に、 Ranges フィールドの右辺値と、 レスポンスで返すリソースのバイト数を引数に与えます。 ranges_type に正規化したリストがベクタで返り、 正常時は関数の値が真になります。 ふるまいを記述すると次のようになります。

2015 年 9 月 14 日修正 アクション表を使う方式に書き換えました。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cctype>
#include "taptests.hpp"

enum {LIMIT_RANGES = 5};
typedef std::vector<std::pair<ssize_t,ssize_t> > ranges_type;
bool canonical_ranges (std::string const& str, ssize_t const len, ranges_type& ranges);

struct {
    std::string input;   ssize_t len;   ranges_type expected;
} SPEC[] = {
    {"bytes=0-9",                1300,  {{0,9}} },
    {"bytes=0-",                 1300,  {{0,1299}} },
    {"bytes=-9",                 1300,  {{1291,1299}} },
    {"bytes=0-0,-1",             1300,  {{0,0}, {1299,1299}} },
    {"bytes=800-20000",          1300,  {{800,1299}} },
    {"bytes=500-600,602-999",    1300,  {{500,600}, {602,999}} },
    {"bytes=500-600,601-999",    1300,  {{500,999}} },
    {"bytes=500-700,601-999",    1300,  {{500,999}} },
    {"bytes=601-999,500-600",    1300,  {{500,999}} },
    {"bytes=601-999,500-700",    1300,  {{500,999}} },
    {"bytes=0-9,12-,30-39,-100", 1300,  {{0,9}, {12,1299}} },
};

int
main ()
{
    test::simple t (12);
    for (auto& x : SPEC) {
        ranges_type got;
        bool r = canonical_ranges (x.input, x.len, got);
        t.ok (r && got == x.expected, x.input);
    }
    {
        ranges_type got;
        t.ok (! canonical_ranges ("bytes=0", 1300, got), "bytes=0");
    }
    return t.done_testing ();
}

//@<canonical_ranges 関数を定義します@>

RFC 7233 から構文を抜粋すると次のようになっています。要するにハイフンを省略してはならず、数値がハイフンの左右に少なくとも1つ必要ということです。

    Range = byte-ranges-specifier

    byte-ranges-specifier = bytes-unit "=" byte-range-set

    bytes-unit = "bytes"

    byte-range-set = 1#(byte-range-spec / suffix-byte-range-spec)
    byte-range-spec = first-byte-pos "-" [last-byte-pos]
    suffix-byte-range-spec = "-" suffix-length
    first-byte-pos = 1*DIGIT
    last-byte-pos = 1*DIGIT
    suffix-length = 1*DIGIT

これから遷移表を作ります。 先頭の bytes= は遷移表による文字列照合の前にチェックしておくことにします。

//@<byte-range-set の遷移表を定義します@>=
    static const int SHIFT[10][6] = {
    //         \s  ',' '-' \d   $
        {   0,  0,  0,  0,  0,  0},
        {   0,  1,  1,  2,  4,  0}, // S1: \s S1 | ',' S1 | '-' S2 | \d S4
        {   0,  0,  0,  0,  3,  0}, // S2: \d S3
        {   0,  7,  8,  0,  3,  9}, // S3: \s S7 | ',' S8 | \d S3 | $ S9
        {   0,  0,  0,  5,  4,  0}, // S4: '-' S5 | \d S4
        {   0,  7,  8,  0,  6,  9}, // S5: \s S7 | ',' S8 | \d S6 | $ S9
        {   0,  7,  8,  0,  6,  9}, // S6: \s S7 | ',' S8 | \d S6 | $ S9
        {   0,  7,  8,  0,  0,  9}, // S7: \s S7 | ',' S8 | $ S9
        {   0,  8,  8,  2,  4,  9}, // S8: \s S8 | ',' S8 | '-' S2 | \d S4 | $ S9
        {   1,  0,  0,  0,  0,  0}, // S9: MATCH
    };
    static const int ACTION[10][6] = {
    //         \s  ',' '-' \d   $
        {   0,  0,  0,  0,  0,  0},
        {   0,  0,  0,  0,  1,  0}, // S1: \s S1 | ',' S1 | '-' S2 | \d S4
        {   0,  0,  0,  0,  1,  0}, // S2: \d S3
        {   0,  3,  3,  0,  1,  3}, // S3: \s S7 | ',' S8 | \d S3 | $ S9
        {   0,  0,  0,  2,  1,  0}, // S4: '-' S5 | \d S4
        {   0,  4,  4,  0,  1,  4}, // S5: \s S7 | ',' S8 | \d S6 | $ S9
        {   0,  5,  5,  0,  1,  5}, // S6: \s S7 | ',' S8 | \d S6 | $ S9
        {   0,  0,  0,  0,  0,  0}, // S7: \s S7 | ',' S8 | $ S9
        {   0,  0,  0,  0,  1,  0}, // S8: \s S8 | ',' S8 | '-' S2 | \d S4 | $ S9
        {   0,  0,  0,  0,  0,  0}, // S9: MATCH
    };

関数 canonical_ranges は、 bytes= のチェックをした後、 その直後から末尾までループを回します。ハイフンの左側を lhs へ、右側を rhs へ値を求めます。値が 32 ビット符号付き整数より大きくなるとエラーにします。つまり、この実装では 2 ギガバイトのリソースまでしか範囲を扱うことができないようになっています。ハイフンの片側にしか数値が存在しないときは、リソースのサイズ len を使って値を求めておいて、 正規化して push する関数に渡します。

//@<canonranges_push 関数を定義します@>

bool
canonical_ranges (std::string const& str, ssize_t const len, ranges_type& ranges)
{
    // 214748364L * 10 + 7 == 0x7fffffffL
    static const ssize_t MAXDECIMAL = 214748364L;
//@<byte-range-set の遷移表を定義します@>
    if (len <= 0)
        return false;
    if (str.compare (0, 6, "bytes=") != 0)
        return false;
    std::string::const_iterator s = str.cbegin () + 6;
    std::string::const_iterator const e = str.cend ();
    int next_state = 1;
    ssize_t lhs = 0;
    ssize_t rhs = 0;
    for (; s <= e; ++s) {
        int c = s < e ? *s : '\0';
        int cls = s == e ? 5
                : '\t' == c ? 1 : ' ' == c ? 1 : ',' == c ? 2 : '-' == c ? 3
                : std::isdigit (c) ? 4 : 0;
        int prev_state = next_state;
        next_state = cls == 0 ? 0 : SHIFT[prev_state][cls];
        if (! next_state)
            return false;
        switch (ACTION[prev_state][cls]) {
        case 1:
            if (rhs > MAXDECIMAL || (rhs == MAXDECIMAL && c > '7'))
                return false;
            rhs = rhs * 10 + c - '0';
            break;
        case 2:
            lhs = rhs;
            rhs = 0;
            break;
        case 3:  // -9
            if (! canonranges_push (len, ranges, std::max (len - rhs, 0), len - 1))
                return false;
            rhs = 0;
            break;
        case 4: // 9-
            if (! canonranges_push (len, ranges, lhs, len - 1))
                return false;
            lhs = 0;
            break;
        case 5: // 0-9
            if (! canonranges_push (len, ranges, lhs, std::min (rhs, len - 1)))
                return false;
            lhs = 0;
            rhs = 0;
            break;            
        }
    }
    return (1 & SHIFT[next_state][0]) != 0;
}

正規化して範囲を ranges リストに push する関数、 canonranges_push では、最初に範囲の指定がおかしくないかどうかをチェックします。 偽を返したときは、416 Range Not Satisfiable のエラーをレスポンスに送信するようにする使い方を考えています。チェックを通過した後は、ranges ベクタを先頭から順に調べて、lhs から rhs の範囲と重なりがある範囲を見つけたら範囲を広げます、もしくは重なりがなく rhs より大きな側にある範囲が見つかると、その前に新しく範囲を挿入します。両方とも、みつからないときは、末尾へ新しく範囲を追加します。

//@<canonranges_push 関数を定義します@>=
static bool
canonranges_push (ssize_t const len, ranges_type& a,
    ssize_t const lhs, ssize_t const rhs)
{
    if (lhs > rhs || lhs > len - 1 || a.size () > LIMIT_RANGES)
        return false;
    for (std::size_t i = 0; i < a.size (); ++i) {
        if (lhs - 1 <= a[i].second && a[i].first <= rhs + 1) {
            a[i].first = std::min (a[i].first, lhs);
            a[i].second = std::max (a[i].second, rhs);
            return true;
        }
        if (rhs < a[i].first) {
            a.insert (a.begin () + i, {lhs, rhs});
            return true;
        }
    }
    a.emplace_back (lhs, rhs);
    return true;
}