(57)【要約】【課題】ＴＣＰのＵＲＧフラグとＵｒｇｅｎｔポインタフィールドが示すＯＯＢ（Ｏｕｔ−ｏｆ−Ｂａｎｄ）データは、受信端末が受信ＴＣＰテキストの文字検索処理をするとき該テキストからＯＯＢデータを除外して検索するのか除外せずに検索するのか、その処理方法をモニタ装置は知ることができない。そのため、モニタ装置はＯＯＢデータを除外したＴＣＰテキストと除外しないＴＣＰテキストの両方でパターン検索を行うため大きな記憶資源を必要としていた。【解決手段】状態遷移で文字列検索を行う際に、文字検索点がＯＯＢデータに達したとき該検索点を１文字分飛び越して文字検索を行い、検索結果が遷移不可になった場合、飛び越し前の文字位置に該検索点を引き戻して検索を再開する殊により、一回のＴＣＰテキスト走査でＯＯＢデータが文字間に挿入されたテキストとＯＯＢデータが通常文字と同じ位置を共有するテキストの文字検索を行う。【選択図】図２
2008017371.tif 000002
【特許請求の範囲】
【請求項１】
状態遷移部と、制御部を具備し、
該状態遷移部はテキストパターンの文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示の判定出力を生成し、一致しない場合遷移不可の判定出力を生成し、
前記制御部はＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、文字検索点を受信テキスト上で開始点から終止点方向に順次移行させ該検索点上の文字を前記状態遷移部に供給しながら該ＯＯＢデータの位置を探索し、その結果、次遷移指示の判定出力を該状態遷移部から得ると該検索点を１文字分前記終止点方向に移行させ、前記ＯＯＢデータ検知前に該状態遷移部から遷移不可の判定出力を得ると照合失敗出力を生成し、前記ＯＯＢデータの検知時点で該ＯＯＢデータの次の文字を検索文字として前記状態遷移部に供給しその判定出力が遷移不可の場合該状態遷移部に前記ＯＯＢデータの位置にある文字を検索文字として前記状態遷移部に供給し、前記ＯＯＢデータの検知後に前記状態遷移部の判定出力が遷移不可の場合照合失敗出力を生成し前記終止点を表示する場合照合成功出力を生成することを特徴とする文字列検索装置。
【請求項２】
請求項１において、前記制御部は前記ＯＯＢデータの位置を検知すると前記検索点の現在位置情報を一時記憶部に保存し、
前記検索点を現在位置に１を加算した位置に移行させ、前記ＯＯＢデータ検知後に遷移不可表示出力を前記状態遷移部から得ると前記検索点を該一時記憶部に保存した位置情報の示す位置に移行させることを特徴とする文字列検索装置。
【請求項３】
状態遷移部と、制御部を具備し、
該状態遷移部はテキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示の判定出力を生成し、一致しない場合遷移不可の判定出力を生成し、
前記制御部はＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、文字検索点を受信テキスト上で開始点から終止点方向に順次移行させ該検索点上の文字を前記状態遷移部に供給しながら該ＯＯＢデータの位置を探索し、その結果、次遷移指示の判定出力を該状態遷移部から得ると該検索点を１文字分前記終止点方向に移行させ、前記ＯＯＢデータ検知前に該状態遷移部から遷移不可の判定出力を得ると照合失敗出力を生成し、前記ＯＯＢデータの検知時点で前記状態遷移部の判定出力が遷移不可の場合前記検索点から１文字分前記終止点方向に移行した位置の文字を検索文字として前記状態遷移部に供給し、前記ＯＯＢデータの検知後に前記状態遷移部の判定出力が遷移不可の場合照合失敗出力を生成し、前記終始点を表示する場合照合成功出力を生成することを特徴とする文字列検索装置。
【請求項４】
モード０またはモード１に設定する動作モード設定部と、状態遷移部と、制御部を具備し、
該状態遷移部はテキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示の判定出力を生成し、一致しない場合遷移不可の判定出力を生成し、
前記制御部はＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、文字検索点を受信テキスト上で開始点から終止点方向に順次移行させ該検索点上の文字を前記状態遷移部に供給しながら該ＯＯＢデータの位置を探索し、その結果、次遷移指示の判定出力を該状態遷移部から得ると該検索点を１文字分前記終止点方向に移行させ、前記ＯＯＢデータ検知前に該状態遷移部から遷移不可の判定出力を得ると照合失敗出力を生成し、
前記制御部はモード０の時、前記ＯＯＢデータの検知時点で該ＯＯＢデータの次の文字を検索文字として前記状態遷移部に供給しその判定出力が遷移不可の場合該状態遷移部に前記ＯＯＢデータの位置にある文字を検索文字として前記状態遷移部に供給し、モード１の時、前記ＯＯＢデータの検知時点で前記状態遷移部の判定出力が遷移不可の場合前記検索点を１文字分前記終止点方向に移行した位置の文字を検索文字として前記状態遷移部に供給し、
前記ＯＯＢデータの検知後に前記状態遷移部の判定出力が遷移不可の場合照合失敗出力を生成し前記終止点を表示する場合照合成功出力を生成することを特徴とする文字列検索装置。
【請求項５】
請求項１、２，３または４において、前記ＯＯＢデータの検知時点において文字位置情報を記憶部に保存し、前記状態遷移部の判定出力が遷移不可の場合該記憶部から保存された文字位置情報を読み出し、該文字位置情報の文字を検索文字として前記状態遷移部に供給することを特徴とする文字列検索装置。
【請求項６】
請求項５において、前記記憶部はバックトラックスタックであることを特徴とする文字列検索装置。
【請求項７】
状態遷移部と、記憶部と、オートマトン処理要求部と、オートマトン処理部を具備し、
該状態遷移部はテキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示出力を生成し、一致しない場合遷移不可表示出力を生成し、
前記オートマトン処理要求部はＴＣＰのＯＯＢデータを含むＴＣＰテキストからなる入力データを受信し、該ＯＯＢデータの位置情報を該入力データから取得し、前記オートマトン処理部の入力値を初期化し、
前記オートマトン処理部は現時点の検索文字列オフセットと前記ＯＯＢデータ位置の間の一致または不一致を検出し、該一致を検出した場合該検索文字列オフセットと遷移状態を前記記憶部に保存し、該検索文字列オフセットに１を加算し、該加算された検索文字列オフセットと該遷移状態を前記状態遷移部に供給し、
該不一致を検出した場合現時点の検索文字列オフセットと遷移状態を前記状態遷移部に供給しその出力を判定し遷移不可であれば前記オートマトン処理要求部に前記記憶部を検索させ、検索文字列オフセットと遷移状態が保存されていれば保存されている情報で前記入力値を再初期化し、該記憶部に検索文字列オフセットと遷移状態が保存されていない場合照合失敗出力を生成することを特徴とする文字列検索装置。
【請求項８】
請求項７において、前記記憶部はバックトラックスタックであることを特徴とする文字列検索装置。
【請求項９】
状態遷移部と、オートマトン処理要求部と、第１オートマトン処理部と、第２オートマトン処理部を具備し、
該状態遷移部はテキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示出力を生成し、一致しない場合遷移不可表示出力を生成し、
前記オートマトン処理要求部はＴＣＰのＯＯＢデータを含むＴＣＰテキストからなる入力データを受信し、該ＯＯＢデータの位置情報を該入力データから取得し、前記オートマトン処理部の入力値を初期化し、
前記第１オートマトン処理部は現時点の検索文字列オフセットと前記ＯＯＢデータ位置の間の一致または不一致を検出し、一致を検出すると前記第２オートマトン処理部を起動し、現時点の検索文字列オフセットと遷移状態を該第２オートマトン処理部に引数として供給し、不一致を検出すると現時点の検索文字列オフセットと遷移状態を前記状態遷移部に供給し、
該第２オートマトン処理部は、
前記第１オートマトン処理部により起動されると、該検索文字列オフセットに１を加算し、該加算された検索文字列オフセットと該遷移状態を前記状態遷移部に供給し、 該不一致を検出した場合現時点の検索文字列オフセットと遷移状態を前記状態遷移部に供給しその出力を判定し、遷移不可出力であれば前記引数に基づき検索前記入力値を再初期化することを特徴とする文字列検索装置。
【請求項１０】
テキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示出力を生成し、一致しない場合遷移不可表示出力を生成する状態遷移部を備えるシステムにおいて、
ａ）ＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、
ｂ）文字検索点を該受信テキスト上で順次開始点から終止点方向に移行させながら前記ＯＯＢデータを探索し、
ｃ）該検索点の文字を検索文字として前記状態遷移部に供給して該状態遷移部の出力を判定し、その判定結果が次遷移指示の場合つぎの文字を検索文字として該状態遷移部に供給し、
ｄ）前記ＯＯＢデータの検知前に前記（ｃ）の判定結果が遷移不可表示の場合照合失敗出力を生成し、
ｅ）前記ＯＯＢデータの検知時点で該ＯＯＢデータの次の文字を検索文字として前記（ｃ）に戻りその判定結果が遷移不可表示の場合該状態遷移部に前記ＯＯＢデータの位置にある文字を検索文字として前記（ｃ）に戻り、
ｆ）前記ＯＯＢデータの検知後に前記（ｃ）の判定結果が遷移不可表示の場合照合失敗出力を生成し、前記終止点を表示する場合照合成功出力を生成することを特徴とする文字列検索方法。
【請求項１１】
テキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示出力を生成し、一致しない場合遷移不可表示出力を生成する状態遷移部を備えるシステムにおいて、
ａ）ＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、
ｂ）文字検索点を該受信テキスト上で順次開始点から終止点方向に移行させながら前記ＯＯＢデータを探索し、
ｃ）該検索点の文字を検索文字として前記状態遷移部に供給して該状態遷移部の出力を判定し、その判定結果が次遷移指示の場合つぎの文字を検索文字として該状態遷移部に供給し、
ｄ）前記ＯＯＢデータの検知前に前記（ｃ）の判定結果が遷移不可表示の場合照合失敗出力を生成し、
ｅ）前記ＯＯＢデータの検知時点で前記（ｃ）の判定結果が遷移不可の場合前記検索点から１文字分前記終止点方向に移行した位置の文字を検索文字として前記（ｃ）に戻り、
ｆ）前記ＯＯＢデータの検知後に前記（ｃ）の判定結果が遷移不可の場合照合失敗出力を生成し、前記終止点を表示する場合照合成功出力を生成することを特徴とする文字列検索方法。
【請求項１２】
テキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示出力を生成し、一致しない場合遷移不可表示出力を生成する状態遷移部を備えるシステムにおいて、
ａ）動作モードを０または１に設定し、
ｂ）ＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、
ｃ）文字検索点を該受信テキスト上で順次開始点から終止点方向に移行させながら前記ＯＯＢデータを探索し、
ｄ）該検索点の文字を検索文字として前記状態遷移部に供給して該状態遷移部の出力を判定し、その判定結果が次遷移指示の場合つぎの文字を検索文字として該状態遷移部に供給し、
ｅ）前記ＯＯＢデータの検知前に前記（ｃ）の判定結果が遷移不可表示の場合照合失敗出力を生成し、
ｆ）動作モードが０に設定されている時、前記ＯＯＢデータの検知時点で該ＯＯＢデータの次の文字を検索文字として前記（ｃ）に戻りその判定結果が遷移不可表示の場合該状態遷移部に前記ＯＯＢデータの位置にある文字を検索文字として前記（ｃ）に戻り、
ｇ）動作モードが１に設定されている時、前記ＯＯＢデータの検知時点で前記（ｄ）の判定結果が遷移不可表示出力であれば前記検索点から１文字分前記終止点方向に移行した位置の文字を検索文字として前記（ｄ）に戻り、
ｈ）動作モードに関係なく、前記ＯＯＢデータの検知後に前記（ｄ）の判定結果が（１）遷移不可表示の場合該状態遷移部に前記ＯＯＢデータの位置にある文字を検索文字として前記（ｄ）に戻り、遷移不可表示の場合（２）照合失敗出力を生成し、（３）前記終止点を表示する場合照合成功出力を生成することを特徴とする文字列検索方法。
【請求項１３】
請求項１０乃至１２のいずれかに記載の文字検索方法を実施するためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は文字列検索装置、方法及びコンピュータプログラムに関し、特にＴＣＰ（Transmission Control Protocol）のＯＯＢ（Out-of-Band）データを含んだ文字列検索装置、方法及びコンピュータプログラムに関する。
【背景技術】
【０００２】
近年、セキュリティの観点上、インターネットを介したサイバー攻撃を防御する手段が必要不可欠となっている。その手段として、侵入検知システム、侵入防御システムであるＩＤＳ（Intrusion Detection System），ＩＰＳ（Intrusion
Prevention System）が挙げられる。これらは、インターネットを流れるデータをモニタリングすることにより、インターネット中のデータにホストのセキュリティの脆弱性を付いてホストに被害を与えるウィルスや、ワームと言ったデータを検出、排除するものである。
【０００３】
これらの検出方法は、モニタリングしているデータを予め登録しておいた複数の攻撃パターンのリストとパターンマッチングさせることにより攻撃を検出する。しかしながら、インターネットを流れるデータの主要プロトコルであるＴＣＰ（Transmission Control Protocol）には、ＯＯＢデータというものが存在する。これは送信者側が受信者側に対して送る緊急用のデータで、本来のデータ受信バッファとは別の格納領域に保存されるデータである。
【０００４】
ＯＯＢデータはＴＣＰのＵｒｇｅｎｔデータとも呼ばれる。ＴＣＰヘッダのＵＲＧフラグが立っている時に、ＴＣＰヘッダのUrgent Pointerフィールドが指示する値から求められる。多くのＯＳ（Operating
System）はUrgent Pointerフィールドが指示する値の次のバイトオフセットの１byteの領域をＯＯＢデータと規定している。
【０００５】
送出するＯＯＢデータはＴＣＰのデータストリーム中に挿入される。受信者はＴＣＰヘッダのＵＲＧフラグとUrgent Pointerフィールドから示されるＯＯＢデータを取り出し、通常のデータストリームとは別バッファに格納する為、受信者が読み出すデータストリームはＯＯＢデータが除外されたものとなる。この為、もし悪意ある送信者が、ウィルスやワームと言ったデータパターンの間にＯＯＢデータを挿入した場合、受信者は、ＯＯＢを除外したデータストリームを読み込んだ際にウィルスやワームの攻撃パターンを読み込んでしまう
。そのため、データをモニタリングしているＩＤＳやＩＰＳは、ＯＯＢデータを除外したパターンをマッチングさせる必要がある。
【０００６】
しかし、受信側は、受信側のＴＣＰの設定変更により、ＯＯＢデータを通常のデータストリームから取り出さず、通常のデータストリームとして読み出すことも可能である（ソケットオプションのＯＯＢ＿ＩＮＬＩＮＥオプション）そして、ＩＤＳやＩＰＳは、受信側はＯＯＢデータを通常のデータストリームから除外して読み出すか、除外せずに読み出すかを知ることが出来ない。故に、ＩＤＳやＩＰＳはＯＯＢデータを除外したものと含んだもの両方で攻撃パターンリストに対するマッチングを行う必要がある。攻撃パターンリストに対するマッチングは、検索するデータとしてテキストを、パターンリストとして複数文字列を考えた時、テキスト中から複数文字列を検索する技術が必要となる。複数の文字列を同時に効率よく検索する方法としてはＡｈｏ−Ｃｏｒａｓｉｃｋ（エイホ・コラシック）法が挙げられる（非特許文献１）これは、検索したい複数文字列リストから有限オートマトンを生成し、それをテキスト上で左から右へ一回走査させて各文字列の出現位置を検出する方法である。
【０００７】
この方法によりテキストの文字数のオーダーで複数の文字列を検索することができる。同様に複数文字列パターンをテキストで検索されている特許は特許文献１に示す技術がある。この技術もオートマトン（状態遷移図）を構成し、複数文字列を検索する。
【０００８】
しかしながら、従来技術は、ＴＣＰのＯＯＢデータのような、検索したい文字列中で除外したものと除外しないものの両方でパターンマッチングしなければいけないものを一回のテキスト走査で検索することは考慮しておらず、除外したテキストパターンと除外しないテキストパターンの２種類を用意してそれぞれについて検索走査する必要がある。
【特許文献１】特願昭６２−２３１０９１
【非特許文献１】Alfred V. Aho and Margaret J.Corasick [Efficient String Matching: AnAidito Bibliographic Search] Communications of the ACM,Vol.18, No6, June1975,pp.333-340
【発明の開示】
【発明が解決しようとする課題】
【０００９】
第１の問題点は、受信端末側でデータをモニタする処理部はＯＯＢを除外するのか除外しないかを知ることができないため、ＯＯＢデータを含む場合ＯＯＢデータを除外したものと除外しないテキスト両方でパターンマッチングができない。
【００１０】
第２の問題点は、従来技術はテキストにＯＯＢデータが混入されていることが想定されていないためＯＯＢデータを除外したテキストと除外しないテキストの両方でパターンマッチングを行うためには、二回の検索が必要になる。また、ＯＯＢデータを含んだものと除外したテキストの両方にデータバッファが必要となるため、記憶資源を大量に消費してしまうことである。
【００１１】
第３の問題点は、従来技術はＴＣＰのＯＯＢデータを含んだテキストと除外したテキストの各にデータ保持用のバッファが必要であるため記憶資源を大きく消費してしまうことである。
【００１２】
本発明の目的は、ＯＯＢデータを含んだものと除外したテキストの両方のパターンマッチングを行うことにより、セキュリティ向上を行うことである。
【００１３】
また、ＯＯＢデータを含んだＴＣＰデータと除外したＴＣＰデータの両方についてパターンマッチングを一回の検索で行うことにより検索時間を短縮することである。
【００１４】
また、ＯＯＢデータを除外したＴＣＰデータとＯＯＢデータを含んだＴＣＰデータをそれぞれ用意して検索する場合より記憶容量を少なくすることである。
【００１５】
また、ＯＯＢデータを除外したＴＣＰデータとＯＯＢデータを含んだＴＣＰデータをそれぞれ用意して検索する場合より処理数を少なくすることである。
【課題を解決するための手段】
【００１６】
本発明の第１の観点において、本発明の文字列検索装置は、状態遷移部と、制御部を具備し、該状態遷移部はテキストパターンの文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示の判定出力を生成し、一致しない場合遷移不可の判定出力を生成し、前記制御部はＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、文字検索点を受信テキスト上で開始点から終止点方向に順次移行させ該検索点上の文字を前記状態遷移部に供給しながら該ＯＯＢデータの位置を探索し、その結果、次遷移指示の判定出力を該状態遷移部から得ると該検索点を１文字分前記終止点方向に移行させ、前記ＯＯＢデータ検知前に該状態遷移部から遷移不可の判定出力を得ると照合失敗出力を生成し、前記ＯＯＢデータの検知時点で該ＯＯＢデータの次の文字を検索文字として前記状態遷移部に供給しその判定出力が遷移不可の場合該状態遷移部に前記ＯＯＢデータの位置にある文字を検索文字として前記状態遷移部に供給し、前記ＯＯＢデータの検知後に前記状態遷移部の判定出力が遷移不可の場合照合失敗出力を生成し前記終止点を表示する場合照合成功出力を生成することを特徴とする。
【００１７】
本発明の第２の観点において、本発明の文字列検索装置は、状態遷移部と制御部とを具備し、該状態遷移部はテキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示の判定出力を生成し、一致しない場合遷移不可の判定出力を生成し、前記制御部はＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、文字検索点を受信テキスト上で開始点から終止点方向に順次移行させ該検索点上の文字を前記状態遷移部に供給しながら該ＯＯＢデータの位置を探索し、その結果、次遷移指示の判定出力を該状態遷移部から得ると該検索点を１文字分前記終止点方向に移行させ、前記ＯＯＢデータ検知前に該状態遷移部から遷移不可の判定出力を得ると照合失敗出力を生成し、前記ＯＯＢデータの検知時点で前記状態遷移部の判定出力が遷移不可の場合前記検索点から１文字分前記終止点方向に移行した位置の文字を検索文字として前記状態遷移部に供給し、前記ＯＯＢデータの検知後に前記状態遷移部の判定出力が遷移不可の場合照合失敗出力を生成し、前記終始点を表示する場合照合成功出力を生成することを特徴とする。
【００１８】
本発明の第３の観点において、本発明の文字列検索装置は、モード０またはモード１に設定する動作モード設定部と、状態遷移部と、制御部を具備し、該状態遷移部はテキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示の判定出力を生成し、一致しない場合遷移不可の判定出力を生成し、前記制御部はＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、文字検索点を受信テキスト上で開始点から終止点方向に順次移行させ該検索点上の文字を前記状態遷移部に供給しながら該ＯＯＢデータの位置を探索し、その結果、次遷移指示の判定出力を該状態遷移部から得ると該検索点を１文字分前記終止点方向に移行させ、前記ＯＯＢデータ検知前に該状態遷移部から遷移不可の判定出力を得ると照合失敗出力を生成し、前記制御部はモード０の時、前記ＯＯＢデータの検知時点で該ＯＯＢデータの次の文字を検索文字として前記状態遷移部に供給しその判定出力が遷移不可の場合該状態遷移部に前記ＯＯＢデータの位置にある文字を検索文字として前記状態遷移部に供給し、モード１の時、
前記ＯＯＢデータの検知時点で前記状態遷移部の判定出力が遷移不可の場合前記検索点を１文字分前記終止点方向に移行した位置の文字を検索文字として前記状態遷移部に供給し、前記ＯＯＢデータの検知後に前記状態遷移部の判定出力が遷移不可の場合照合失敗出力を生成し前記終止点を表示する場合照合成功出力を生成することを特徴とする。
【００１９】
本発明の第４の観点において、本発明の文字列検索方法はテキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示出力を生成し、一致しない場合遷移不可表示出力を生成する状態遷移部を備えるシステムにおいて、（ａ）ＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、（ｂ）文字検索点を該受信テキスト上で順次開始点から終止点方向に移行させながら前記ＯＯＢデータを探索し、（ｃ）該検索点の文字を検索文字として前記状態遷移部に供給して該状態遷移部の出力を判定し、その判定結果が次遷移指示の場合つぎの文字を検索文字として該状態遷移部に供給し、（ｄ）前記ＯＯＢデータの検知前に前記（ｃ）の判定結果が遷移不可表示の場合照合失敗出力を生成し、（ｅ）前記ＯＯＢデータの検知時点で該ＯＯＢデータの次の文字を検索文字として前記（ｃ）に戻りその判定結果が遷移不可表示の場合該状態遷移部に前記ＯＯＢデータの位置にある文字を検索文字として前記（ｃ）に戻り、（ｆ）前記ＯＯＢデータの検知後に前記（ｃ）の判定結果が遷移不可表示の場合照合失敗出力を生成し、前記終止点を表示する場合照合成功出力を生成することを特徴とする。
【００２０】
本発明の第５の観点において、本発明の文字列検索方法はテキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示出力を生成し、一致しない場合遷移不可表示出力を生成する状態遷移部を備えるシステムにおいて、（ａ）ＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、（ｂ）文字検索点を該受信テキスト上で順次開始点から終止点方向に移行させながら前記ＯＯＢデータを探索し、（ｃ）該検索点の文字を検索文字として前記状態遷移部に供給して該状態遷移部の出力を判定し、その判定結果が次遷移指示の場合つぎの文字を検索文字として該状態遷移部に供給し、（ｄ）前記ＯＯＢデータの検知前に前記（ｃ）の判定結果が遷移不可表示の場合照合失敗出力を生成し、（ｅ）前記ＯＯＢデータの検知時点で前記（ｃ）の判定結果が遷移不可の場合前記検索点から１文字分前記終止点方向に移行した位置の文字を検索文字として前記（ｃ）に戻り、（ｆ）前記ＯＯＢデータの検知後に前記（ｃ）の判定結果が遷移不可の場合照合失敗出力を生成し、前記終止点を表示する場合照合成功出力を生成することを特徴とする。
【００２１】
本発明の第６の観点において、本発明の文字列検索方法はテキストパターンの各文字とその遷移状態を記憶し、外部から入力文字が供給されると該テキストパターンを検索し、該入力文字と検索された文字を相互に照合し検索結果として、一致する場合次遷移指示出力を生成し、一致しない場合遷移不可表示出力を生成する状態遷移部を備えるシステムにおいて、（ａ）動作モードを０または１に設定し、（ｂ）ＴＣＰのＯＯＢデータを含むＴＣＰテキストを受信し、（ｃ）文字検索点を該受信テキスト上で順次開始点から終止点方向に移行させながら前記ＯＯＢデータを探索し、（ｄ）該検索点の文字を検索文字として前記状態遷移部に供給して該状態遷移部の出力を判定し、その判定結果が次遷移指示の場合つぎの文字を検索文字として該状態遷移部に供給し、（ｅ）前記ＯＯＢデータの検知前に前記（ｃ）の判定結果が遷移不可表示の場合照合失敗出力を生成し、（ｆ）動作モードが０に設定されている時、前記ＯＯＢデータの検知時点で該ＯＯＢデータの次の文字を検索文字として前記（ｃ）に戻りその判定結果が遷移不可表示の場合該状態遷移部に前記ＯＯＢデータの位置にある文字を検索文字として前記（ｃ）に戻り、（ｇ）動作モードが１に設定されている時、前記ＯＯＢデータの検知時点で前記（ｄ）の判定結果が遷移不可表示出力であれば前記検索点から１文字分前記終止点方向に移行した位置の文字を検索文字として前記（ｄ）に戻り、（ｈ）動作モードに関係なく、前記ＯＯＢデータの検知後に前記（ｄ）の判定結果が（１）遷移不可表示の場合該状態遷移部に前記ＯＯＢデータの位置にある文字を検索文字として前記（ｄ）に戻り、遷移不可表示の場合（２）照合失敗出力を生成し、（３）前記終止点を表示する場合照合成功出力を生成することを特徴とする。
【発明を実施するための最良の形態】
【００２２】
本発明の第１の実施の形態について図１を参照して説明する。本文字列検索装置は複数の検索パターンが有限状態のオートマトン（状態遷移図）として格納されているオートマトン状態遷移部１０４、オートマトン処理要求部１０２とオートマトン処理部１０３からなる制御部１００、と該オートマトン処理部の出力データを一時的に保持するデータバッファ１０５から構成される。
【００２３】
状態遷移部１０４は、後述する図４に１例として示す如く、制御データが専用の文字位置に挿入された「挿入型またはＯＯＢ型」テキスト(ｖｉｒｕｓ)と制御データと通常データが同じ文字位置を共有する「共有型またはインライン型」テキスト（ｗｏｒｍ）のような複数のテキストパターンの各文字とその遷移状態を記憶し、制御部１００から供給される入力テキスト１の各文字と該記憶された各文字を相互に比較し、その結果、次遷移可能な文字が存在する場合は次遷移を指示する判定出力を生成し、次遷移可能な文字が存在しない場合は遷移不可を表す判定出力を生成し、検索点がテキストの終始点に達した場合終了フラグを生成する。この終了フラグはパターンマッチング（照合）が成功したことを意味する。
なお、後述する如く、本発明において検索過程における遷移不可を表す判定出力は必ずしもパターンマッチングの失敗を意味しない。
【００２４】
制御部１００はＴＣＰのＯＯＢデータを含むＴＣＰテキスト１０１を取得すると該テキストを文字単位で検索点を移行させながら入力テキスト上を走査する。制御部１０００は検索点を順次テキスト上で移行させながら該ＯＯＢデータの位置の探索し、かつ検索点上の文字を状態遷移部１０４に供給する。その結果、状態遷移部１０４の判定出力が次遷移を指示する場合、検索点を次文字の位置に進める。一方、制御部はＯＯＢデータの位置を検知した時点で検索点を１文字分終止点方向に進めることによりＯＯＢデータ位置を飛ばす。従って、第１実施形態において、制御部はＯＯＢデータについて状態遷移部１０４にその判定結果を求めない。このように検索点を１文字分終止点方向に進めた直後に状態遷移部１０４の判定出力が遷移不可を表す場合、制御部１０００は検索点を次文字位置から１文字分減算した位置に後退させる。
【００２５】
このような検索処理を文字列の開始点から終止点まで実行することによりＴＣＰのＯＯＢデータが専用の文字位置に挿入された「挿入型」テキストとＯＯＢデータと通常データが同じ文字位置を共有する「共有型」テキストのいずれも一回の検索走査でパターンマッチングさせることができる。
【００２６】
次に図２及び図３は制御部１００を構成するオートマトン処理要求部１０２とオートマン処理部１０３の動作をそれぞれ表すフローチャートである。入力ＴＣＰテキスト１が検索パターンにマッチするか否かの検索処理はオートマトン処理要求部１０２が先ずオートマトン処理部１０３に入力値を供給し、次に処理部１０３が入力テキストの文字列を文字単位に状態遷移部１０４に供給し検索パターンの文字列と該状態遷移部から判定結果を取得する。
【００２７】
図２において、オートマトン処理要求部１０２は、まず入力ＴＣＰテキスト１０１からＴＣＰテキスト"T"とＯＯＢデータフィールドの位置を示すＯＯＢデータオフセット"U"を取得し（ステップ２０１）、次にステップ２０２において、オートマトン処理部１０３の複数の初期値を設定する。即ち、入力ＴＣＰテキストＴに入力ＴＣＰテキスト１が設定され、ＯＯＢデータオフセット"U"にＴＣＰデータのUrgentフラグが立っている時のＴＣＰヘッダのUrgentポインタフィールドの値"U0"が設定され、検索文字列オフセット"P"とオートマトンステート"S"には、それぞれ、ＴＣＰテキストの先頭文字の位置を示すオフセット値"P0"と初期状態"S0"が設定される。
【００２８】
次に、図３において、オートマトン処理部１０３は初期化された入力データ（ＴＣＰテキスト"T"、ＯＯＢデータオフセット"U"、検索文字列オフセット"P"、オートマトンステート"S"）の供給に応じ、ステップ３０１においてフラグ"i"を０に設定し、ステップ３０２でＯＯＢデータオフセット"U"と検索文字列オフセット"P"を比較し互いに等しいか否かを判定する。テキスト上の検索（走査）点がOOBデータフィールドの位置にくると、ＯＯＢデータオフセット"U"と文字列オフセット"P"は互いに等しくなる。ステップ３０２の判定がNOであればフローはステップ３０３に進み、YESであればステップ３０７に進みフラグ"i"を１に設定し、ステップ３０８でデータバッファ１０５に現時点における文字列オフセットPと遷移状態Sを書き込み、ステップ３０９で文字列オフセットPに１を加算し、ステップ３０３に進む。
【００２９】
ステップ３０３において、処理部１０３は状態遷移部１０４にデータT, P, Sを供給し、ステップ３０４で該状態遷移部から検索結果を取得する。処理部１０３はつぎの判定ステップ３０５でこの検索結果としての判定出力をチェックし、</a>判定出力が遷移指示（遷移可能）であれば状態遷移部１０４から出力データとして次の文字列オフセットP_oと次の遷移状態S_oを得る。これらの値で状態遷移部１０４の次の入力値を再初期化し（ステップ３０６）、判定ステップ３１０に進みフラグ"i"が０か１かを判定する。フラグ"i"が０であればまだＯＯＢデータは検知されていないので、フローはステップ３０２に戻り、フラグ"i"が１であれば既にＯＯＢデータは検知されているのでフローはステップ３０３に進む。
【００３０】
ステップ３０５の判定結果が遷移不可であれば、フローは判定ステップ２０３（図２）に戻りデータバッファ１０５を参照しデータの有無を調べる。データが格納されていなければ「パターンマッチング不成功」を表示する出力を出力部１０６に供給し、データバッファ１０５にデータが格納されていればステップ２０３からステップ２０４に進み格納されているデータを用いオートマトン処理部１０３の入力値を再初期化し、ステップ３１０（図３）に戻る。再初期化されたデータはＯＯＢデータオフセット"U"と検索文字列オフセット"P"が互いに等しかったときのデータなので、処理部１０３の入力値は文字列オフセットP(U=P)、オートマトンステートS(U=P)となる。
【００３１】
ステップ３０５の判定結果が終了フラグであれば、パターンマッチングは成功したのでフローはステップ２０６（図２）で「パターンマッチング成功」の出力を出力部１０６に供給する。
【００３２】
このオートマトン処理部１０３による「ＯＯＢ位置飛び越し検索」により、ＯＯＢ「挿入型」テキストの場合、状態遷移部１０４は全通常文字について検索結果を出力する。一方、ＯＯＢ「共有型」テキストの場合、この「飛び越し検索」のためＯＯＢ位置のつぎの通常文字について状態遷移部１０４は遷移不可を出力することになり、その結果オートマトン処理部１０３は検索点をＯＯＢ位置に後退させる。この後退検索により状態遷移部１０４はＯＯＢ「共有型」テキストについても正常な検索結果を生成する。
【００３３】
次に第１実施形態の動作について具体的な例を挙げて説明する。図４の（ａ）を参照すると、検知したい文字列パターンとして"ｖｉｒｕｓ"と"ｗｏｒｍ"を仮定する。この２つの文字列パターンからオートマトンATを状態遷移部１０４に格納する。
【００３４】
このオートマトンATに対し、図４（ｂ）に示すようにＯＯＢデータが文字間に挿入された「ＯＯＢ挿入型」入力文字列ＥＸ１のマッチング動作の例を示す。即ち、文字列が"ｖｉｒｏｕｓ”で、このうち"o"がＯＯＢデータである。
【００３５】
この文字列が入力された時のオートマトン処理要求部１０２が処理部１０３に供給する初期値は、ＯＯＢデータオフセットU＝３、検索文字列オフセットP＝０,オートマトンステートS＝０となる。
【００３６】
次に処理部１０３は以下に示す状態遷移部１０４への入力の供給が行われ遷移可能であれば遷移指示出力として次オートマトンステートＳ_ｏと次検索文字列オフセットP_oを取得する。
１回目
入力：オートマトンステート０，検索文字列オフセット０
出力：オートマトンステート１，検索文字列オフセット１
２回目
入力：オートマトンステート１，検索文字列オフセット１
出力：オートマトンステート２，検索文字列オフセット２
３回目
入力：オートマトンステート２，検索文字列オフセット２
出力：オートマトンステート３，検索文字列オフセット３
状態遷移部１０３の３回目の出力時点で検索文字列オフセットＰとＯＯＢデータオフセットＵが互いに等しくなるため（ステップ３０２)、検索文字列オフセット（Ｐ＝３）とオートマトンステート（Ｓ＝３）をデータバッファ２４に書き込み（ステップ３０８)、文字列オフセットＰを一つ進める(ステップ３０９)。これにより次の検索文字列オフセットＰは４となる。
４回目
入力：オートマトンステート３，検索文字列オフセット４
出力：オートマトンステート４，検索文字列オフセット５
５回目
入力：オートマトンステート４，検索文字列オフセット５
出力：オートマトンステート５，結果：「終了」
上記のように５回目の要求で、入力ＴＣＰテキストＥＸ１がテキストパターン“ｖｉｒｕｓ”に一致する。
【００３７】
次に、図４（ｃ）にＯＯＢデータが通常の文字の位置に含まれている［共有型またはインライン型］テキストＥＸ２、即ち文字列が“ｗｏｒｍ”で、このうちの“ｏ”がＴＣＰのＯＯＢデータである例を示す。
【００３８】
このＴＣＰテキストが入ってきた時の動作は、オートマトン処理要求部１０２は処理部１０３の初期値をＯＯＢデータオフセットＵ＝１、検索文字列オフセットＰ＝０、オートマトンステートＳ＝０に設定する。次に、処理部１０３と状態遷移部１０４の間で以下の入力と出力が生成される。
１回目
入力：オートマトンステート０，検索文字列オフセット０
出力：オートマトンステート６，検索文字列オフセット１
１回目の状態遷移部１０４への要求後の時点で検索文字列オフセットＰがＯＯＢデータオフセットＵに等しくなるため、
処理部１０３はＰ＝１とＳ＝６をデータバッファ１０５に書き込み（ステップ３０８）、文字列オフセットＰを一つ進める（ステップ３０９）。これにより次の検索文字列オフセットＰは２となる。
２回目
入力：オートマトンステート６，検索文字列オフセット２
出力：遷移不可（＝非整合）
２回目の入力時点で、遷移可能のオートマトンステートが存在しないため、
「遷移不可」を表す出力が状態遷移部１０４から供給される。その直後、データバッファ１０５にデータが保存されているので（ステップ２０３)、オートマトン処理要求部１０２はこれを取り出し、検索文字列オフセット"Ｐ"をＯＯＢデータのオフセットの値"1"に、オートマトンステート"Ｓ"をＯＯＢオフセット検出時のステート"6"に再初期化し（ステップ２０４)、ステップ３０３に戻る。この結果、オートマトン処理部１０３は検索処理を再開し状態遷移部１０４との間で以下の処理を行う。
３回目
入力：オートマトンステート６，検索文字列オフセット１
出力：オートマトンステート７，検索文字列オフセット２
４回目
入力：オートマトンステート７，検索文字列オフセット２
出力：オートマトンステート８，検索文字列オフセット３
５回目
入力：オートマトンステート８，検索文字列オフセット３
出力：オートマトンステート９，「終了フラグ」
上記の様にＥＸ２の入力ＴＣＰテキストが５回の処理でパターン"worm”に整合することが判明する。
【００３９】
上述の如く、「ＯＯＢ挿入型」と「ＯＯＢ共有型」の両ＴＣＰテキストのパターンマッチングが一回の検索走査で完了する。さらに、２種類のＴＣＰテキストについて記憶領域を用意しなくても、検索文字列オフセットがＯＯＢデータ上にある時の一時ステートの格納領域を用意しておくだけで双方とも検索できるので、必要とする記憶資源が少ない。
【００４０】
次に、本発明の第２の実施の形態について図５、６、７、８を参照して説明する。図５を参照すると、第２実施形態の文字列検索装置の図１との相違点はデータバッファ１０５を使用せず、制御部５００をオートマトン処理要求部５０１，第１オートマトン処理部５０２と第２オートマトン処理部５０３により構成したことである。第２実施形態のオートマトン処理要求部５０１が
第１オートマトン処理部５０２に要求する回数は一回だけとなる。
【００４１】
図６において、オートマトン処理要求部５０１は、入力ＴＣＰテキスト１０１からＴＣＰテキスト"T"とＯＯＢデータフィールドの位置を示すＯＯＢデータオフセット"U"を取得し（ステップ６０１）、ステップ６０２において第１オートマトン処理部５０２の複数の初期値Ｔ，Ｕ，ＰとＳを設定する。
【００４２】
図７において、第１オートマトン処理部５０２はステップ７０１でフラグ“ｉ”を０に設定し、ステップ７０２でＯＯＢデータ位置をチェックし、Ｕ＝Ｐでなければ、ステップ７０３でＴ，Ｐ，Ｓを状態遷移部１０４に供給し検索を要求し、検索結果をステップ７０４で取得し、その結果を判定し（ステップ７０５）、遷移可能であれば遷移指示の出力値を取得し判定ステップ７０７に至る。フラグ“ｉ”が０であれば判定ステップ７０２が再び実行される。ＯＯＢデータが入力されるまで上記の処理が繰り返し実行される。遷移不可の判定出力を状態遷移部１０４から受け取ると第１オートマトン処理部５０２はステップ７０５からステップ６０３（図２）に進み、オートマトン処理要求部５０１から「パターンマッチング不成功」が出力部１０６に出力される。
【００４３】
図７において、検索点がＯＯＢデータ位置に達するとステップ７０２でＵがＰに等しくなり、第１オートマトン処理部５０２はステップ７０２からステップ７０８に進みフラグ“ｉ”を１に設定し、現時点の値（Ｔ，Ｐ，Ｓ）を引数として第２オートマトン処理部５０３に引き渡し該処理部を起動し（ステップ７０９）、ステップ７０３に進む。
【００４４】
図８において、第２オートマトン処理部５０３はステップ８０１で第1オートマトン処理部５０2から引き受けたＰとＳ値をメモリに格納し、ステップ８０２でＰに１を加算し、ステップ８０３で状態遷移部１０４に設定された入力値を供給し、その検索結果を得る（ステップ８０４）。ステップ８０５で検索結果が判定され、遷移可能であれば遷移指示の出力値を取得しステップ８０３に戻る。ＯＯＢデータ検出後の各文字がパターンの対応する文字と一致する毎に上記の処理が繰り返し実行される。
【００４５】
ステップ８０５で遷移不可の判定出力が状態遷移部１０４から返信されると
ステップ６０３（図６）に戻る。ステップ８０５で終了フラグが検出されると図６のステップ６０４に戻り「パターンマッチング成功」を出力する。
【００４６】
上述の如く第２実施形態では、ＯＯＢデータを起点として複数の処理部で並列にパターンマッチング処理ができるため、パターン検索時間がＯＯＢを除外した時と除外しない時のどちらか一方でＴＣＰテキストを走査した場合の時間と同じとなる。
【００４７】
本発明の第３の実施の形態の文字検索装置について図９、１０、１１を参照して説明する。図９に図示の如く、該文字検索装置は検索モード選択部９０１を具備しており、該設定部が制御部９００のオートマトン処理要求部９０２に接続され、第１実施形態同様、オートマトン処理部９０３が該処理要求部９０２と状態遷移部１０４との間に設けられている。検索モード選択部
９０１は動作モード０と１のいずれかを選択し、“０”の場合文字検索装置はＯＯＢデータを除外せず検索し遷移不可が発生した場合ＯＯＢデータ位置を飛び越し（除外し）て検索を再開する。
【００４８】
一方、“１”の場合は第１実施形態同様、先ずＯＯＢデータを飛び越して検索し、その直後に遷移不可が発生した場合ＯＯＢデータ位置に戻り検索を再開する。即ち、モード０の場合、「ＯＯＢデータを飛び越さない検索（即ちＯＯＢデータを含んだ検索）」が「ＯＯＢデータ飛び越し検索」に優先するモードであり、モード１の場合はこの逆で、「ＯＯＢデータ飛び越し検索」が「ＯＯＢデータ非飛び越し検索」に優先するモードである。
【００４９】
図１０を参照すると、オートマトン処理要求部９０２は第１実施形態同様、入力ＴＣＰテキスト１０１からＴＣＰテキストＴとＯＯＢデータオフセットＵを取得し（ステップ１００１）、ステップ１００２で、オートマトン処理部９０３
の初期値を設定し、該処理部を起動する。
【００５０】
図１１のステップ１１０１で、オートマトン処理部９０３は起動するとフラグ“ｉ”を０に設定し、ステップ１１０２でＯＯＢデータ位置をチェックし、Ｕ＝Ｐでなければ、ステップ１１０３でＴ，Ｐ，Ｓを状態遷移部１０４に供給し検索を要求し、検索結果をステップ１１０４で取得し、その結果を判定し（ステップ１１０５）、遷移可能であれば遷移指示の出力値を取得しステップ１１０６で処理部９０３の初期値を遷移指示の出力値に再初期化し、判定ステップ１１０７に進みフラグ“ｉ”が０か１かを判定する。フラグ“ｉ”が０であれば判定ステップ１１０２が再び実行され、ＯＯＢデータが入力されるまで上記の処理が繰り返し実行される。
【００５１】
やがて検索点がＯＯＢデータ位置に達すると、ステップ１１０２でＵ＝Ｐとなり、ステップ１１０８でｉ＝１に設定され、つぎにモードＭが０か１か判定され、０であればステップ１１０３に、１であればステップ１１１０に進みデータバッファ１０５にＰとＳ値を書き込み、Ｐの値に１を加算し（ステップ１１１１）、ステップ１１０３に進みＴ，Ｐ，Ｓを状態遷移部１０４に供給し検索を要求し、ステップ１１０４において検索結果を状態遷移部１０４から取得し、その結果を判定する（ステップ１１０５）。ステップ１１０５の判定が「遷移不可」であると処理部９０３は図１０の判定ステップ１００３に戻る。
【００５２】
図１０において、処理要求部９０２はステップ１００３においてデータバッファ１０５のデータ有無を判定し、データ有りと判定するとつぎの判定ステップ１００４でモードＭが０か１かを判定する。
【００５３】
Ｍ＝１の場合、処理要求部９０３はステップ１００５に進みデータバッフア１０５からＰとＳの値を取り出しオートマトン処理部１０３の入力値を再初期化し、ステップ１１０７に戻る。再初期化されたデータはＯＯＢデータオフセット"U"と検索文字列オフセット"P"が互いに等しかったときのデータであり、処理部１０３の入力値は文字列オフセットP(U=P)、オートマトンステートS(U=P)となる。
【００５４】
Ｍ＝０の場合、処理要求部９０３はステップ１００６に進みデータバッフア１０５からＰの値を取り出しこれに１を加算した値に再初期化しこれを文字列オフセットP(U=P＋１)とし、次にＳの値を取り出しこれをＰの値に再初期化しオートマトンステートS(U=P)とし、ステップ１１０７に戻る。ステップ１１０３の判定がデータ無しの場合、処理要求部９０３はステップ１００７に進み「パターンマッチング不成功」を処理要求部９０２に出力する。
【００５５】
一方、図１１において、処理要求部９０３は状態遷移部１０４から終了フラグを受け取ると（ステップ１１０５）処理要求部９０２に終了フラグを受け取ったことを伝える。これに応じ、処理要求部９０２は「パターンマッチング成功」信号を出力部１０６に伝達する（ステップ１００８、図１０）。
【００５６】
図４のオートマトンＡＴと入力テキストＥＸ１、ＥＸ２を利用しモード０の場合の第３実施形態の動作を図１２を参照して説明する。なお、モード１の場合の動作は図４と同じなので説明は省略する。
【００５７】
図１２（ａ）図示のオートマトンＡＴに対し、図１２（ｂ）に示す入力文字列"ｖｉｒｏｕｓ”が入力された時のオートマトン処理要求部９０２が処理部９０３に供給する初期値は、図４と同様ＯＯＢデータオフセットU＝３、検索文字列オフセットP＝０,オートマトンステートS＝０となる。
【００５８】
次に処理部９０３は以下に示す状態遷移部１０４への入力の供給が行われ遷移可能であれば遷移指示出力として次オートマトンステートＳ_ｏと次検索文字列オフセットP_oを取得する。
１回目
入力：オートマトンステート０，検索文字列オフセット０
出力：オートマトンステート１，検索文字列オフセット１
２回目
入力：オートマトンステート１，検索文字列オフセット１
出力：オートマトンステート２，検索文字列オフセット２
３回目
入力：オートマトンステート２，検索文字列オフセット２
出力：オートマトンステート３，検索文字列オフセット３
４回目
入力：オートマトンステート３，検索文字列オフセット３
出力：遷移不可
状態遷移部９０３はこの４回目の入力でＯＯＢデータを検知し（ｉ＝１）、かつ、ステップ１１０５（図１１）の判定出力が遷移不可となるためステップ１００６（図１０）で文字列オフセットＰに１が加算され次の検索文字列オフセットＰは４となる。
５回目
入力：オートマトンステート３，検索文字列オフセット４
出力：オートマトンステート４，検索文字列オフセット５
６回目
入力：オートマトンステート４，検索文字列オフセット５
出力：オートマトンステート５，「終了フラグ」
上記のように６回目の要求で、
入力ＴＣＰテキストＥＸ１がテキストパターン“ｖｉｒｕｓ”に一致する。
【００５９】
次に、図１２（ｃ）の文字列ＥＸ２（ｗｏｒｍ）が入ってきた時、図４と同様オートマトン処理要求部９０２は処理部９０３の初期値をＯＯＢデータオフセットＵ＝１、検索文字列オフセットＰ＝０、オートマトンステートＳ＝０に設定する。次に、処理部９０３と状態遷移部１０４の間で以下の入力と出力が生成される。
１回目
入力：オートマトンステート０，検索文字列オフセット０
出力：オートマトンステート６，検索文字列オフセット１
２回目
入力：オートマトンステート６，検索文字列オフセット１
出力：オートマトンステート７，検索文字列オフセット２
３回目
入力：オートマトンステート７，検索文字列オフセット２
出力：オートマトンステート８，検索文字列オフセット３
４回目
入力：オートマトンステート８，検索文字列オフセット３
出力：オートマトンステート９，「終了フラグ」
この様に４回の処理で入力文字列"worm”の検索結果が判明する。
【００６０】
この第３実施形態は、パターンマッチングを行うＴＣＰストリームに対してＯＯＢデータを除外したパターンと除外しないパターンのいずれを優先させるべきかが予め分かっている場合に便利である。
【００６１】
次に本発明の第４の実施の形態について図面を参照して説明する。文字列のパターン検索に使われる状態遷移のオートマトンは、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである公知のＤＦＡ（Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ）と、次の遷移先が一意に決定しない公知のＮＦＡ（Ｎｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ）の２種類に分けられる。本実施形態は次の遷移先が一意に決定しないＮＦＡの場合、遷移分岐点の情報を「バックトラックスタック」という状態保持部に格納し、遷移先のうちの一つに進み、その遷移先の処理終了後にバックトラックスタックの情報を取得して遷移点からのもう１つの遷移先を辿るという処理を行う。
【００６２】
本実施形態に置いて検知したいパターンが正規表現パターンの”（［ａｂ］＊ｃ）＊ａｄ”というパターンであるとする。（ここで、”［ａｂ］”の正規表現はａかｂのどちらか、＊は直前の表現の０個以上の繰り返しを示す。）オートマトンステート０の時に、検索文字列オフセットの文字が"ａ”であると、ステート１に遷移する経路と、ステート２に遷移する経路の両方が存在することになり、次に遷移する状態が一意に決まらない。文字列“ａｂ”が入力された場合状態遷移部１０４に要求する動作は以下のようになる。
【００６３】
図１６に一例を示す。初期値がオートマトンステート０，検索文字列オフセット０の時、同一文字"a"について２つの遷移先（ステート１とステート２）が存在する仮定すると、現在の状態であるオートマトンステート０と文字列オフセット０をバックトラックスタックに保存しそのうちの１つであるステート１を遷移先として任意に選び遷移する。
１回目
入力：“Ｓ＝０”，“Ｐ＝０”
出力：“Ｓ_o ＝1”，“Ｐ_o ＝１”
２回目
入力：“Ｓ＝１”，“Ｐ＝１”
出力：遷移不可
２回目の入力時点で、遷移可能なオートマトンステートが存在しないので状態遷移部１０４は遷移不可の判定を下しバックトラックスタックから“Ｓ＝０”と“Ｐ＝０”を読み出し、ステート２に遷移する。
３回目
入力：“Ｓ＝０”，“Ｐ＝０”
出力：“Ｓ_o＝２”，“Ｐ_o ＝１”
４回目
入力：“Ｓ＝２”，“Ｐ＝1”
出力：“Ｓ_o ＝３”，終了フラグ
第４実施形態はＮＦＡで使われるバックトラックスタックに検索文字列オフセットがＯＯＢデータ上にある時の一時状態を共存させるというものである。
【００６４】
図１３を参照すると、本実施の形態は第一の実施の形態で存在した図１のＯＯＢ用データバッファ１０５の代わりに、バックトラックスタック１３０１を使用している点が異なる。第４実施形態の文字列検索装置の制御部１３００は、第１実施形態で使用したデータバッファ１０５の代わりにバックトラックスタック１３０１からデータを取り込んで再初期化を行う。該制御部はオートマトン処理要求部１３０２とオートマトン処理部１３０３からなる。
【００６５】
図１４において、オートマトン処理要求部１３０２が実行するステップ１４０１乃至１４０６は図２の処理要求部１０３が実行するステップ２０１乃至２０６にそれぞれ対応しており処理内容は同じである。
【００６６】
図１５において、オートマトン処理部１３０３は初期化された入力データ（Ｔ，Ｕ，Ｐ，Ｓ）の供給に応じ、ステップ１５０１においてフラグ"ｉ”を０に設定し、ステップ１５０２でＯＯＢデータオフセットＵと検索文字列オフセットＰを比較し互いに等しいか否かを判定する。ステップ１５０２の判定がNOであればフローはステップ１５０３に進み、YESであればステップ１５１１に進みフラグ"ｉ”を１に設定し、ステップ１５１２でバックトラックスタック１３０１にPとSを書き込み、ステップ１５１３でPに１を加算し、ステップ１５０３に進む。
【００６７】
ステップ１５０３において、同一条件で複数の遷移状態が存在するか否かが判定され、ＮＯであればフローはステップ１５０６に進み、ＹＥＳであればステップ１５０４でバックトラックスタックにPとSを書き込み、ステップ１５０５でつぎの遷移先として任意の遷移状態を選択し、ステップ１５０６に進む。
【００６８】
ステップ１５０６で、処理部９０３は状態遷移部１０４にデータT, P, Sを供給し、ステップ１５０７で該状態遷移部から検索結果を取得する。 処理部９０３はつぎの判定ステップ１５０８でこの検索結果としての判定出力をチェックし、判定出力が遷移指示（遷移可能）であれば状態遷移部１０４から出力データとして次の文字列オフセットP_oと次の遷移状態S_oを得る。これらの値で状態遷移部１０４の次の入力値を再初期化し（ステップ１５０９）、判定ステップ１５１０に進みフラグ"ｉ”が０か１かを判定する。フラグ"ｉ”が０であればまだＯＯＢデータは検知されていないので、フローはステップ１５０２に戻り、フラグ"ｉ”が１であれば既にＯＯＢデータは検知されているのでフローはステップ１５０３に進む。
【００６９】
第４実施形態は、バックトラックを実装したオートマトンによる検索処理であれば、検索文字列オフセットがＯＯＢデータ上にある時の一時情報を別に設けたバッファを使用せずバックトラックスタックを共有することにより、記憶領域の構成とアクセスする為の処理が簡潔になる。
【図面の簡単な説明】
【００７０】
【図１】本発明の第１の実施の形態における文字列検索装置のブロック図。
【図２】第１実施形態のオートマトン処理要求部のフローチャート。
【図３】第１実施形態のオートマトン処理部のフローチャート。
【図４】第１実施形態の動作例を説明する図。
【図５】本発明の第２の実施の形態における文字列検索装置のブロック図。
【図６】第２実施形態のオートマトン処理要求部のフローチャート。
【図７】第２実施形態の第１オートマトン処理部のフローチャート。
【図８】第２実施形態の第２オートマトン処理部のフローチャート。
【図９】本発明の第３の実施の形態における文字列検索装置のブロック図。
【図１０】第３実施形態のオートマトン処理要求部のフローチャート。
【図１１】第３実施形態のオートマトン処理部のフローチャート。
【図１２】第３実施形態の動作例を説明する図。
【図１３】本発明の第４の実施の形態における文字列検索装置のブロック図。
【図１４】第４実施形態のオートマトン処理要求部のフローチャート。
【図１５】第４実施形態のオートマトン処理部のフローチャート。
【図１６】第４実施形態の動作例を説明する図。
【符号の説明】
【００７１】
１０１  入力TCPテキスト
１００  制御部
１０２、５０２，９０２，１３０２  オートマトン処理要求部
１０３、５０３，９０３，１３０３  オートマトン処理部
１０４  オートマトン状態遷移部
１０５  データバッファ
１０６  パターンマッチング結果出力部
９０１  検索モード選択部
１３０１  バックトラックスタック
ＡＴ  オートマトン
ＥＸ１  文字列例
ＥＸ２  文字列例
ＡＴ２  NFAのオートマトン
ＥＸ３  NFAの文字列例
【図１】
2008017371.tif 000003
【図２】
2008017371.tif 000004
【図３】
2008017371.tif 000005
【図４】
2008017371.tif 000006
【図５】
2008017371.tif 000007
【図６】
2008017371.tif 000008
【図７】
2008017371.tif 000009
【図８】
2008017371.tif 000010
【図９】
2008017371.tif 000011
【図１０】
2008017371.tif 000012
【図１１】
2008017371.tif 000013
【図１２】
2008017371.tif 000014
【図１３】
2008017371.tif 000015
【図１４】
2008017371.tif 000016
【図１５】
2008017371.tif 000017
【図１６】
2008017371.tif 000018