0

環境

Web アクセス ログを解析する場合、ボットを人間のユーザー エージェントから分離する必要があります。

それらのリストを手動で作成し、ボットのようなパターン (たとえば、botを含む) を抽出しました。次に、受信アクセス ログをリアルタイムで検証するパターンのリスト (最大 300 項目) を取得します。私の (非効率的な) アルゴリズムが任意のパターンを探すため、時間が経つにつれて、これはかなりのボトルネックになりました。DoS に対する脆弱性を意味するパフォーマンスの低下を無視したとしても。

コード (Java)

String userAgent;
List<Pattern> botPatterns;

    for (Pattern botPattern : botPatterns)
    {
        if (botPattern.matcher(userAgent).find())
        {
            return true;
        }
    }
    return false;

すでに調査済みの回答

WURFL を使用して

これは単純な解決策かもしれませんが、結果が不正確になることがあります。今のところ、組み込みのソリューションは避けたいと思います。

ユーザーエージェントのキャッシュを使用する

ユーザー エージェント文字列をハッシュマップに格納することで、結果をキャッシュすることができます。ただし、これによりパフォーマンスは向上しますが、ランダムに生成されたユーザー エージェント文字列による単純な DoS 攻撃に対する脆弱性が高まります。

質問

一定数の正規表現パターン (m) に対して多数 (N) の文字列を照合する効率的なアルゴリズムはありますか?

編集：ベンチマーク回答

実際のデータと、ランダムに生成されたユーザー エージェント文字列を使用して、@stemm の回答をベンチマークしました。テストを 10 秒間実行し、計算時間を平均しました。キャッシュは、サイズ 5000 の単純な LFU ehcache です。

ここに私の結果があります：

パターンループ

キャッシュなし

実際のデータ: 101us

ランダムデータ: 193us

キャッシュあり

実際のデータ: 4us

ランダムデータ: 203us

単一のパターン

キャッシュなし

実際のデータ: 100us

ランダムデータ: 160us

キャッシュあり

実際のデータ: 3us

ランダムデータ: 154us

結論

  • 実際の状況では、キャッシングが最も効果的なソリューションです。
  • 1 つのパターンを使用すると、複数のパターンをループする場合に比べて 25% のゲインが得られます。
  • キャッシュは、私が思っていたほど DoS に対して脆弱ではありません。

人々の回答とコメントに感謝します。

4

2 に答える 2

1

パターンの数が固定されている場合は、パターンを表現する有限ステート マシンを構築できます。これにより、パフォーマンスが大幅に向上します。ただし、このソリューションには、ロジックと FSM を表すための追加の開発が必要です。

パターンの数がある例[abc、abd、acd、dab]

有限ステート マシンは次のようになります。

start -> a -> b -> c -> finish
                -> d -> finish
           -> c -> d -> finish
      -> d -> a -> b -> finish

FSM は、状態数が制限された順序付きグラフのように考えることができます。abdこれらのパターンで文字列を一致させたいとします。最初から始めて、a -> b -> d に遭遇して終了します。Thta は、文字列がパスから復元できるパターンに一致することを意味します。*などの機能を備えたより複雑なパターンは、?状態をそれ自体にリンクする ( *) か、この状態をまったくスキップする( ) ことで表すことができます?。

于 2012-09-03T07:36:54.017 に答える
1

主なアイデアは、持っているすべての正規表現を含む収集パターンを作成することです。

たとえば、次の正規表現のいずれかに一致する文字列を検索したい場合:^\d+$または。したがって、それらをそのような正規表現に組み合わせることができます。^[aA]+$^[a-z\s]+$(^\d+$|^[aA]+$|^[a-z\s]+$)

サンプル Java コード:

public class Test {

    public static Pattern gather( String... patterns ) {
        StringBuilder finalRegexBuilder = new StringBuilder( "(" );
        for ( String ptr : patterns ) {
            finalRegexBuilder.append( ptr ).append( "|" );
        }
        finalRegexBuilder.setLength( finalRegexBuilder.length() - 1 );
        finalRegexBuilder.append( ")" );
        return Pattern.compile( finalRegexBuilder.toString() );
    }

    public static void main( String[] args ) {
        Pattern regex = gather( "^\\d+$", "^[aA]+$", "^[a-z\\s]+$" );

        System.out.println( regex.toString() ); // (^\d+$|^[aA]+$|^[a-z\s]+$)

        System.out.println( regex.matcher( "1235" ).find() ); // true
        System.out.println( regex.matcher( "1235fdjg" ).find() ); // false
        System.out.println( regex.matcher( "AAAaaaAaa" ).find() ); // true
        System.out.println( regex.matcher( "hello world" ).find() ); // true
    }
}

実際、正規表現の根底にあるメカニズムは有限状態マシンです。したがって、上記のコードには、@mishadoff が話した FSM があります。

于 2012-09-03T09:28:59.347 に答える