Rust で「まぎらわしいアルファベット」を検出したい

Rust のお勉強中です。勉強したことのアウトプットとして、スパムフィルター機能を備えた POP3 プロキシを作成しています。

スパムメール(迷惑メール)にはいろいろ特徴がありますが、そのひとつとして、「英語以外のまぎらわしいアルファベットを使っている」というものがあります。たとえば、「AMAZON」の代わりに「AMAZОN」と書いてあったりします。アルファベットの「O」(オー)が違います。人間の目では区別できないですよね。

作成中のスパムフィルターでは、この特徴をスパムの指標のひとつとして使いたい。

ちなみに、Rust 標準ライブラリの char には、Unicode の文字種を判定する関数が用意されています。関数 char::is_alphabetic() は、英語のアルファベットだけではなく、他の言語のアルファベットや、日本語の漢字ひらがなカタカナに対しても、true を返します。 Unicode での「アルファベット」は、とても意味が広いみたいですね。また、関数 char::is_ascii_alphabetic() は、ASCII 文字のアルファベットに対してだけ true を返してくれます。

最初に考えた案は、Unicode の文字種(コードポイントの属する分類名?)を使えないか、というものです。しかし、ちょっと調べたところでは、これを簡単に行う方法はなさそうでした。

次に、lingua クレートを使う案を考えました。 lingua クレート (https://crates.io/crates/lingua) は、与えられた文字列が「どの言語で書かれたものか?」を判定するクレートです。このクレートの基本的な機能(使われている Unicode 文字の種類の判定)を使って、日本語と英語とそれ以外とを区別できるんじゃないか、と考えたわけです。これはうまく動きました。書いてみたコードをこの記事の末尾に掲載しておきます。

しかし、なんというか、lingua クレートを使う案は、オーバーキル感が否めません・・・。

そこで、いま流行りの LLM な AI に質問してみることにしました。 検索エンジン bing のページから Copilot が簡単に使えるので(ログインすら不要)、試してみました。その結果、うまく動作する正規表現が得られました。

Regex::new(r"[\p{Alphabetic}&&[^\p{ASCII}\p{Hiragana}\p{Katakana}\p{Han}\p{Punct}ー]]").unwrap();

以下、Copilot とのやりとりをそのまま掲載します。ご参考まで!

Copilot とのやりとり

あなたは日本語で応答してください。あなたは Rust 言語のプログラマです。日本語と英語が混じった文字列について、英語以外のアルファベット(たとえばキリル文字)が含まれているかを判定する処理のソースコードを提示してください。

了解しました!英語以外のアルファベットが含まれているかを判定する処理のRustコードをお見せしますね。

use regex::Regex;

fn contains_non_english_alphabets(s: &str) -> bool {
    // Unicodeの範囲に基づいて英語以外のアルファベットを判定
    let non_english_regex = Regex::new(r"[^\u0000-\u007F\u00A0-\u00FF\u0100-\u017F]").unwrap();
    non_english_regex.is_match(s)
}

fn main() {
    let text = "これはtestです"; // 例として日本語と英語の混在文字列
    if contains_non_english_alphabets(text) {
        println!("英語以外のアルファベットが含まれています。");
    } else {
        println!("英語以外のアルファベットは含まれていません。");
    }
}

このコードでは、正規表現を使用して英語以外のアルファベットが文字列に含まれているかどうかを判定します。キリル文字などの他のアルファベットもチェックできます。この例では、日本語と英語が混在する文字列を判定対象にしています。何か他に手伝えることはありますか?

提示されたコードは誤っています。なぜなら、この正規表現では、日本語の文字(漢字など)もマッチしてしまうからです。修正案を提示してください。

指摘ありがとうございます。それでは、日本語の文字(漢字など)を除外して、英語以外のアルファベットを判定する修正版のコードをお見せします。

use regex::Regex;

fn contains_non_english_alphabets(s: &str) -> bool {
    // 英語のアルファベットと日本語の文字を除外した正規表現
    let non_english_regex = Regex::new(r"[^\p{Latin}\p{Hiragana}\p{Katakana}\p{Han}]").unwrap();
    non_english_regex.is_match(s)
}

fn main() {
    let text = "これはtestです"; // 例として日本語と英語の混在文字列
    if contains_non_english_alphabets(text) {
        println!("英語以外のアルファベットが含まれています。");
    } else {
        println!("英語以外のアルファベットは含まれていません。");
    }
}

このコードでは、英語のアルファベット(Latin)と日本語の文字(ひらがな、カタカナ、漢字)を除外して、それ以外の文字が含まれているかどうかを判定します。これでキリル文字など他のアルファベットもチェックできます。また指摘などあれば教えてくださいね。

提示されたコードの正規表現は、ピリオドなどの記号にもマッチしてしまいます。修正案を提示してください。

その通りですね。ピリオドや他の記号を除外する修正案を示します。以下のコードでは、英語のアルファベット(Latin)、日本語の文字(ひらがな、カタカナ、漢字)、および基本的な記号を除外するようにしています。

use regex::Regex;

fn contains_non_english_alphabets(s: &str) -> bool {
    // 英語のアルファベット、日本語の文字、および記号を除外した正規表現
    let non_english_regex = Regex::new(r"[^\p{Latin}\p{Hiragana}\p{Katakana}\p{Han}\p{Punct}]").unwrap();
    non_english_regex.is_match(s)
}

fn main() {
    let text = "これはtestです。"; // 例として日本語と英語の混在文字列
    if contains_non_english_alphabets(text) {
        println!("英語以外のアルファベットが含まれています。");
    } else {
        println!("英語以外のアルファベットは含まれていません。");
    }
}

この修正版の正規表現は、句読点や記号を考慮しています。これでさらに精度が上がるはずです。何か他にお手伝いできることはありますか?

提示されたコードの正規表現は、日本語の長音記号 「ー」にもマッチしてしまいます。修正案を提示してください。

ありがとうございます。長音記号「ー」を除外するために、もう少し修正を加えます。

use regex::Regex;

fn contains_non_english_alphabets(s: &str) -> bool {
    // 英語のアルファベット、日本語の文字、句読点、基本的な記号、長音記号を除外した正規表現
    let non_english_regex = Regex::new(r"[^\p{Latin}\p{Hiragana}\p{Katakana}\p{Han}\p{Punct}ー]").unwrap();
    non_english_regex.is_match(s)
}

fn main() {
    let text = "これはtestですー。"; // 例として日本語と英語の混在文字列
    if contains_non_english_alphabets(text) {
        println!("英語以外のアルファベットが含まれています。");
    } else {
        println!("英語以外のアルファベットは含まれていません。");
    }
}

これで、日本語の長音記号「ー」も考慮されています。こちらでどうでしょうか?他にも修正が必要な点があれば教えてください。

提示されたコードの正規表現は、ASCII 文字以外の英語アルファベットにもマッチしてしまいます。英語アルファベットについては ASCII 文字のみマッチするようにしてください。

なるほど、ASCII文字のみの英語アルファベットにマッチするように正規表現を修正しました。

use regex::Regex;

fn contains_non_english_alphabets(s: &str) -> bool {
    // ASCII範囲の英語アルファベット、日本語の文字、句読点、基本的な記号、長音記号を除外した正規表現
    let non_english_regex = Regex::new(r"[^\x00-\x7F\u3040-\u309F\u30A0-\u30FF\u4E00-\u9FFF\u3000-\u303Fー]").unwrap();
    non_english_regex.is_match(s)
}

fn main() {
    let text = "これはtestですー。"; // 例として日本語と英語の混在文字列
    if contains_non_english_alphabets(text) {
        println!("英語以外のアルファベットが含まれています。");
    } else {
        println!("英語以外のアルファベットは含まれていません。");
    }
}

これで、ASCII範囲の英語アルファベットのみにマッチするように修正されています。いかがでしょうか?他にも修正や質問があれば教えてくださいね。

Rust 標準ライブラリの関数 char::is_alphabetic() に相当する正規表現を提示してください。

char::is_alphabetic() に相当する正規表現は、Unicodeのアルファベット全体をカバーする必要があります。つまり、基本ラテン文字だけでなく、全ての国のアルファベットに対応することを意味します。以下のような正規表現がそれに該当します。

use regex::Regex;

fn contains_alphabetic_chars(s: &str) -> bool {
    // Unicodeのアルファベットに該当する正規表現
    let alphabetic_regex = Regex::new(r"\p{Alphabetic}").unwrap();
    alphabetic_regex.is_match(s)
}

fn main() {
    let text = "これはtestですー。"; // 例として日本語と英語の混在文字列
    if contains_alphabetic_chars(text) {
        println!("アルファベットが含まれています。");
    } else {
        println!("アルファベットは含まれていません。");
    }
}

この正規表現は、全てのUnicodeアルファベット文字をマッチします。これが char::is_alphabetic() に相当する処理となります。お試しください!他にも質問があれば教えてください。

Rust で、正規表現 [\p{Alphabetic}] と正規表現 [^\p{ASCII}] の両方にマッチする文字列にマッチする単一の正規表現を提示してください。

もちろんです。正規表現 [\p{Alphabetic}] はすべてのアルファベットにマッチし、[^\p{ASCII}] はASCII範囲外のすべての文字にマッチします。この両方にマッチする文字列を見つけるには、ASCII範囲外のアルファベットを対象にします。

以下の単一の正規表現がその目的を達成します:

use regex::Regex;

fn main() {
    let text = "Example 例 тест مثال"; // 例として様々なアルファベットを含む文字列
    let regex = Regex::new(r"[\p{Alphabetic}&&[^\p{ASCII}]]").unwrap();
    let matches: Vec<_> = regex.find_iter(text).collect();

    for m in matches {
        println!("{}", m.as_str());
    }
}

この正規表現は、[\p{Alphabetic}&&[^\p{ASCII}]] で、ASCII範囲外のアルファベット文字にマッチします。これでどうでしょうか?他に何かお手伝いできることはありますか?

以上を参考に、完成させたのが次の正規表現となります:

Regex::new(r"[\p{Alphabetic}&&[^\p{ASCII}\p{Hiragana}\p{Katakana}\p{Han}\p{Punct}ー]]").unwrap();

正規表現の中で文字クラスを指定するときに && 記号を使って入れ子にできるということは、初めて知りました。他の言語の正規表現エンジンでも使えるのかしら??

ちなみに、Copilot が提案してきた「Unicode コードポイントの範囲を指定する」正規表現(\u4E00-\u9FFF とか)は、 \p{Han} という Unicode character class 指定に比べて当たり判定が小さいので、ダメです。たとえば、漢字の「𠮷」(下の横棒が長い「𠮷野家」の字)がマッチしなくなってしまいます。

結論: Copilot は優秀だけど、提案された内容をちゃんと吟味できないとダメ

lingua クレート使う案

当初、正規表現では無理だと考えたので、lingua クレートを使う方法を実装しました。

lingua クレート (https://crates.io/crates/lingua) は、与えられた文字列が「どの言語で書かれたものか?」を判定するクレートです。このクレートの基本的な機能(使われている Unicode 文字の種類の判定)だけを使って、日本語と英語とそれ以外とを区別できるんじゃないか、と考えたわけです。

まず、lingua クレートのサンプルコードをそのまま使って、「すべての言語の中からどの言語の文字かを推定する」機能を使ってみました。

lazy_static! {
    static ref DETECTOR: lingua::LanguageDetector = lingua::LanguageDetectorBuilder::from_all_languages().build();
    static ref EXCEPTION_CHARS: Vec<char> = vec!['ー']; // these characters are "is_alphabetic()=true", but do not recognize a Japanese character
}

let is_suspicious_alphabet = |c: &char| {
    if !c.is_alphabetic() {
        return false;
    }
    if EXCEPTION_CHARS.contains(c) {
        return false;
    }
    // see https://crates.io/crates/lingua
    let lang = DETECTOR.detect_language_of(*c);
    let is_suspicious = match &lang {
        &Some(lingua::Language::English) => false,
        &Some(lingua::Language::Japanese) => false,
        _ => true,
    };
    if is_suspicious {
        println!("suspicious-alphabet: {} ({:?})", *c, lang);
    }
    is_suspicious
};

しかし、from_all_language() の結果は、安定しませんでした。普通の ASCII アルファベットに対して、English 以外のいろいろな言語を返してきてしまいます。

そこで、選択肢を英語と日本語のみに限定して、判定させることにしました。英語と日本語のそれぞれについて、「どれくらいその言語っぽいか」を数値化してもらい、その数値が十分大きければ OK、というようにしました。

lazy_static! {
    static ref LANGUAGES_FOR_DETECTOR: Vec<lingua::Language> = vec![lingua::Language::English, lingua::Language::Japanese];
    static ref DETECTOR: lingua::LanguageDetector = lingua::LanguageDetectorBuilder::from_languages(&LANGUAGES_FOR_DETECTOR).build();
    static ref EXCEPTION_CHARS: Vec<char> = vec!['ー']; // these characters are "is_alphabetic()=true", but do not recognize a Japanese character
}

let is_suspicious_alphabet = |c: &char| {
    if !c.is_alphabetic() {
        return false;
    }
    if EXCEPTION_CHARS.contains(c) {
        return false;
    }
    // see https://crates.io/crates/lingua
    let confidence_values = DETECTOR.compute_language_confidence_values(*c).into_iter().collect::<HashMap<lingua::Language, f64>>();
    let is_english = confidence_values[&lingua::Language::English] > 0.9;
    let is_japanese = confidence_values[&lingua::Language::Japanese] > 0.9;
    let is_ok = (is_english && c.is_ascii_alphabetic()) || is_japanese;
    if !is_ok {
        println!("suspicious-alphabet: {} ({:?})", *c, confidence_values);
    }
    !is_ok
};

これで、ちゃんとキリル文字とかを検出できるようになりました。

しかし、まぁ、文字種判定に lingua クレートを使うのは、オーバーキルもいいところだと思います。計測はしていませんが、きっと処理も重いと思われます。

正規表現で実現できるなら、そのほうがいいですねー!

ACM 論文「QUIC is not Quick Enough over Fast Internet」を読んだ

アメリカの学会 ACM で発表された論文「QUIC is not Quick Enough over Fast Internet」を読んだので、ブログ記事にしておきます。

論文の結論を先に書いておくと、

  • 500Mbps を越える高速かつ高品質なネットワーク接続環境での話(有線接続とか WiFi 7 とか 5G モバイルとかを想定)。
  • 大きなファイル (~1GB) のダウンロードに要する時間とかで、体感できる差が観測できる(9秒 vs 18秒)。
  • クライアント側の OS (Linux/macOS/Windows) やソフトウェア (cURL/Chromium/Firefox) に関わらず同様に差が観測できる。
  • サーバ側のソフトウェア (OpenLiteSpeed/Nginx-quic) に関わらず同様に差が観測できる(OS は Ubuntu 18.04)。
  • QUIC が遅い原因は、「UDP であること」「プロトコルスタックがユーザ空間で実装されていること」である。つまり、QUIC を QUIC たらしめている特徴がそのまま原因になっている。

論文の概要

論文の概要(グラフとか)は、Gigazine さんの記事を参照してください(手抜きですみません):

論文では、Ubuntu 18.04 のデスクトップ PC を2台用意して、ほぼ Ethernet 直結、という構成で、いろいろ評価しています。モバイル回線などを想定した帯域制限は、Linux の tc コマンドを使って模擬しています。モバイル回線の模擬では、歩行パターンと自動車走行パターンの2パターンを用いています。

論文では、いろいろなクライアントプログラム(=ユーザ空間のプロトコルスタックの実装)を使って評価しています:

  • cURL
  • quic_client by Chromium Project
  • Chromium
  • Google Chrome
  • Microsoft Edge
  • Opera
  • Firfox

いずれのクライアントプログラムでも、「CPU 負荷が高い」「ファイルダウンロードが遅い」という傾向は変わらず。

また、Linux (Ubuntu) だけでなく、macOS や Windows でも評価してみたが、傾向は変わらず。

以下、原因の解析です。

パケットトレース (tcpdump) を見てみると、以下のことがわかった:

  • Linux kernel で処理された「受信パケット数」が一桁多い (744K vs 58K)。これは、NIC の TCP オフロード機能で複数の TCP セグメントが1回にまとめられた影響。
  • ACK が返ってくるまでの round-trip time (RTT) が一桁遅い (16.2ms vs 1.9ms)。ping RTT は 0.23ms なので、クライアント側での ACK 送信処理の時間が支配的な要因。

クライアント側での CPU 負荷が高い原因について、Linux kernel のプロファイリングを解析したところ、以下のことがわかった:

  • Linux カーネル内部でのパケット受信処理 netif_receive_skb の呼び出し回数が一桁多い (231K vs 15K)
  • システムコールの回数が一桁多い (17K vs 4K)
  • カーネル空間からユーザ空間にデータをコピーする処理 copy_user_enhanced_fast_string の呼び出し回数が多い (4K vs 3K)

クライアントプログラム (Chromium) のプロファイリングを解析したところ、以下のことがわかった:

  • パケットデータをソケットから読み出す処理が重い (0.248sec vs 0.037sec)
  • パケットのペイロードを解析する処理が重い (0.310sec vs 0.084sec)
  • ACK を返す処理が重い (2.972sec vs 0sec)

このような傾向が出る原因は、ひとつは、「TCP ではなく UDP を使っている」からで、

  • TCP は単純な byte stream なので複数の TPC セグメントをまとめて処理するのが簡単だが、QUIC のように multiplex している UDP ではそもそも困難。
  • したがって、TCP のように NIC のプロトコルオフロード機能が効かない。すべてのパケットを1個ずつ処理しないといけない。

もうひとつの原因は、「プロトコルスタックがユーザ空間で実装されている」からで、

  • 1パケットごとにカーネル空間からユーザ空間にデータコピーを行っているので、重い。
  • ACK を返す処理は、TCP ならカーネル内で効率的に折り返せるが、QUIC ではユーザ空間で行うので、重い。

というストーリーになっています。

以上の結果から、論文では、以下のような改善策を提案しています:

  • NIC のプロトコルオフロード機能(複数の UDP パケットをまとめる処理)を活用する。ただし、このオフロード機能が使えるかはクライアントのプラットホームに依るので、一般化は困難。
  • QUIC の UDP パケットに適した NIC プロトコルオフロード機能を実装する(受信側で複数パケットをまとめる処理とか、送信レート制御とか)。
  • クライアント側での QUIC 実装ロジックを工夫する(“delayed QUIC ACK” を実装するとか、recvmsg の代わりに recvmmsg を呼ぶとか)。
  • クライアント側をマルチスレッド処理にして、複数の QUIC 接続を使って並列ダウンロードする。

感想

QUIC が遅い原因は、「UDP であること」「プロトコルスタックがユーザ空間で実装されていること」ということで、つまり、QUIC を QUIC たらしめている特徴がそのまま原因になっています。したがって、今回の測定結果を劇的に改善するのは、難しそうです。

UDP パケットの処理を高速化するには NIC のオフロード機能が有効と言っていますが、そもそも UDP の場合はオフロード機能を実装するのが難しいとも言っていて、まぁ、一般的な NIC に実装されそうにはありません。

プロトコルスタックがユーザ空間で実装されているのでオーバヘッドが大きい、という点については、改善できる点はあるにしても、本質的にはどうにもならなさそうです。個人的には、HPC 向け高速ネットワークの InfiniBand などで採用されている User-level 通信が使えれば、カーネルを介すオーバヘッドはなくなるので、思想的には最適解な気がします。ただ、一般的な Ethernet NIC に実装されるのは難しそうですが・・・。

あと、1点気になるところとして、「サーバとクライアントとのネットワーク距離が遠い場合には、また違った傾向が出てくるのでは?」と思いました。論文では言及がありませんでしたが、ACK が返ってくるタイミングや、送信レート制御処理などに影響があるので、もしかしたら別の知見が得られるかも??

いずれにしても、QUIC プロトコルに関する新しい知見で、おもしろい論文でした。

p.s. この論文、arXiv でもダウンロードできちゃうみたいですが、読むならちゃんと ACM で買いましょう。無料ユーザ登録して、15ドルで買えます。