レート制限と総当たり対策のアルゴリズム原理

レート制限を「アルゴリズム」として見る

レート制限の本質は、到着するイベント列を受理するか拒否するかを、過去の到着履歴に基づいて決めるオンライン判定問題です。設計者が選ぶアルゴリズムは、(1) どれだけのバーストを許すか、(2) どれだけのメモリと計算量を要するか、(3) 分散環境でどれだけ正確に協調できるか、という3軸でトレードオフします。基礎的な使い分けは レート制限 で扱ったので、本稿は各方式の内部挙動・誤差・分散一貫性、そして総当たりへの実効的な防御を原理から掘り下げます。

まず「レート」には2つの異なる量が混ざることを区別します。平均レート（長期的な毎秒あたりの上限）とバースト許容量（瞬間的にまとめて通せる量）です。アルゴリズムの個性は、この2つをどう独立に制御できるかに現れます。

トークンバケットとリーキーバケット：双対だが別物

トークンバケットは、容量 capacity のバケツに毎秒 rate 個のトークンを補充し、リクエスト1件ごとに1個消費します。空なら拒否します。重要なのは、トークンを毎回タイマーで足すのではなく、判定時に経過時間から遅延計算する点です。これで時間刻みのタイマーが不要になり、ストレージには「最後の補充時刻」と「残トークン数」の2値だけを置けます。

def allow(state, rate, capacity, now):
    # 前回判定からの経過ぶんを補充。上限は capacity でクランプ
    elapsed = now - state.ts
    state.tokens = min(capacity, state.tokens + elapsed * rate)
    state.ts = now
    if state.tokens >= 1:
        state.tokens -= 1
        return True      # 受理
    return False         # 拒否（429）

このとき許されるバーストは「補充が追いつかない短時間に最大 capacity 件」です。平均は rate に収束し、瞬間集中は capacity まで許す。2つのパラメータが直交して効くのがトークンバケットの強みです。

リーキーバケットは発想が逆で、出力を一定速度に固定します。到着はキュー（バケツ）に溜まり、底の穴から毎秒 rate 件だけ流れ出ます。キューが溢れたら捨てます。出力が常に平滑化され、下流は完全に一定ペースのトラフィックしか受けません。

ウィンドウ方式：境界バーストと近似精度

固定ウィンドウは「毎分0秒でカウンタをゼロに戻し、区間内の件数を数える」最も単純な方式です。しかし区間の境界に構造的欠陥があります。上限が毎分100件なら、ある分の最後の1秒に100件、次の分の最初の1秒にさらに100件を送れば、約2秒の間に200件——上限の2倍が通ります。攻撃者から見れば、これは確実に悪用できる抜け穴です。

これを塞ぐのがスライディングウィンドウです。2つの実装があります。

• スライディングウィンドウログ：各リクエストのタイムスタンプを保存し、判定時に「現在から過去 W 秒」より古いものを捨て、残った件数を数えます。完全に正確ですが、上限が高いキーではタイムスタンプの配列が膨らみ、メモリと計算量が件数に比例します。
• スライディングウィンドウカウンタ：現区間と直前区間の2つのカウンタだけを持ち、ウィンドウが直前区間にかかる割合で加重平均して推定します。メモリ一定で境界バーストを大幅に緩和できる、実務での定番近似です。

# スライディングウィンドウカウンタ（近似）
# 直前区間の件数を、ウィンドウが直前にかかる割合ぶん按分して足す
overlap = (window - elapsed_in_current) / window   # 0..1
estimate = current_count + prev_count * overlap
allow = estimate < limit                            # 推定が上限未満なら受理

この近似は、直前区間の到着が一様分布だと仮定して件数を按分します。実際の到着が偏っていると推定が真値からずれますが、固定ウィンドウの2倍問題は消え、ログ方式のメモリ爆発も避けられます。正確さが要るならログ、一定メモリでよいならカウンタ、という選択になります。

分散環境での一貫性

複数ノードに散らばったカウンタをどう一貫させるか。代表的な戦略は3つです。

最も多いのは Redis などの共有ストアへ原子的に集約する方式です。ここで肝心なのは、読み取りと書き込みの間に他ノードが割り込む競合（read-modify-write の競合）を避けることです。INCR は単一の原子的操作ですが、固定ウィンドウしか作れません。トークンバケットやスライディングウィンドウは複数の値を一貫して更新する必要があるため、サーバー側スクリプト（Lua）で複数コマンドを1つの原子的単位として実行するのが定石です。これで「補充→消費→残量書き戻し」が他の判定に割り込まれず、カウンタずれを防げます。

**トークン配分（リース）**は、グローバルな上限プールから各ノードへトークンの塊を貸し出し、ノードはローカルで消費して尽きたら追加リースを取りに行く方式です。判定のたびに通信せずに済むため低レイテンシで、かつグローバル上限は超えません。ただしリースを持ったノードが落ちると、その未使用ぶんが一時的に死蔵される点に注意します。

総当たり対策：頻度制御だけでは破られる

レート制限は総当たり（ブルートフォース）対策の土台ですが、IP 単位の頻度制御だけでは現代の攻撃に不十分です。攻撃の形を分けて考えます。

• 古典的ブルートフォース：1アカウントに多数のパスワードを試す。これは「アカウント＋IP」単位の試行回数制限と、失敗時の指数バックオフ（失敗ごとに待ち時間を倍化）で現実的時間内に成立しなくできます。
• クレデンシャルスタッフィング：漏洩した「正しい」ユーザー名とパスワードの組を、多数のサイトへ大量に試す。1アカウントあたりの試行は1〜数回と少なく、IP も大量のプロキシ・ボットネットに分散します。アカウント単位でもIP単位でも閾値に達しないため、頻度制御をすり抜けます。
• パスワードスプレー：少数のよくあるパスワード（Password1! 等）を、多数のアカウントへ薄く広く試す。これもアカウント単位ではロックに達しません。

つまりクレデンシャルスタッフィングとスプレーは、頻度を意図的に閾値以下に保つことで設計上レート制限を回避します。対抗には、頻度以外のシグナルが要ります。

CAPTCHA と Proof-of-Work：自動化のコストを上げる

頻度で区別できない攻撃には、人間か自動化かを区別する、あるいは自動化のコストを引き上げる仕組みを重ねます。

• CAPTCHA：人間には容易で機械には難しいタスク（画像認識、振る舞い解析）で人間性を判定します。現代の方式は明示的なパズルより、マウス軌跡・タイミング・デバイス指紋などの受動的シグナルでスコアリングし、疑わしいときだけチャレンジを出す方向に進化しています。ただし CAPTCHA 解決を代行する有人・AI サービスが存在するため、単独では完全な防御になりません。
• Proof-of-Work（PoW）：クライアントに、検証は軽いが計算は重い問題（例：先頭 k ビットが0になるハッシュを探す）を解かせ、その解を添えさせます。サーバーは1回のハッシュで検証できますが、攻撃者は大量試行のたびに重い計算を強いられ、大規模自動化の単価が跳ね上がります。難易度 k を動的に上げれば、攻撃の経済性を能動的に破壊できます。

PoW チャレンジの例（先頭 k ビットが 0 のハッシュを探す）:
  サーバー: challenge と難易度 k を発行
  クライアント: H(challenge, nonce) の先頭 k ビットが 0 になる nonce を総当たりで探索
                期待試行回数は約 2^k 回（指数的に重い）
  サーバー: nonce を受け取り H を1回計算して検証（軽い）

→ 検証は O(1)、生成は O(2^k)。この非対称性が自動化の単価を押し上げる。

PoW の利点は、CAPTCHA と違って人間の操作を要求せず正規ユーザーの体験を損ねにくい点と、サーバー側に攻撃者ごとの状態を持たずに済む点です。難点は、正規の低性能端末（古いスマートフォン等）にも計算負担がかかること、そして専用ハードを持つ攻撃者には相対的に効きが弱まることです。

実務では単一の銀の弾丸を置かず、頻度制御（レート制限）→ デバイス／IP 評価 → 疑わしいときだけ CAPTCHA／PoW → 認証段で MFA という多層で、各層が別のシグナルを使って攻撃の経済性を段階的に破壊します。

まとめ

レート制限のアルゴリズムは、平均レートとバースト許容量をどう独立に制御するかで性格が決まります。トークンバケットは容量ぶんのバーストを許して即時に受理・拒否し、リーキーバケットは出力を平滑化して下流を保護する——双対だが許すバースト形状が逆です。GCRA は両者を時刻1つで表す統一的な見方を与えます。固定ウィンドウは境界で上限の2倍が通る欠陥があり、スライディングウィンドウはログ方式で正確に、カウンタ方式でメモリ一定の近似として塞ぎます。

分散環境では正確さ・レイテンシ・可用性が三すくみになり、共有ストアへの原子的集約・ローカル＋同期・トークン配分のいずれを選ぶかは要件次第です。総当たり対策としては、頻度制御は古典的ブルートフォースには効くものの、閾値以下に抑えるクレデンシャルスタッフィングやパスワードスプレーには単独で無力で、デバイス指紋・CAPTCHA・PoW・MFA を重ねて自動化のコストと突破後の価値を同時に削ぐのが要点です。可用性側の全体像は DoS/DDoS の増幅原理と緩和アーキテクチャ と併せて押さえると、頻度ベース防御の位置づけが立体的に見えてきます。