[Backport 200 - Backport #8716][Open] segmation fault 正規表現で大量のグループを利用時

alcina · August 1, 2013, 2:58pm

Issue #8716 has been reported by taka-yoshi (taka-yoshi taka).

Backport #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi (taka-yoshi taka)
Status: Open
Priority: Normal
Assignee:
Category:
Target version:

WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。

#Ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]

taka-yoshi_Staka-yo · August 4, 2013, 1:57am

Issue #8716 has been updated by nobu (Nobuyoshi N.).

Category set to regexp
Status changed from Feedback to Assigned
Target version set to current: 2.1.0
ruby -v set to trunk

regexec.c:match_at()で呼ばれるSTACK_INITがサイズを考慮せずにxallocaしているため、スタックオーバーフローしています。

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi (taka-yoshi taka)
Status: Assigned
Priority: Normal
Assignee:
Category: regexp
Target version: current: 2.1.0
ruby -v: trunk
Backport:

WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。

#Ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]

taka-yoshi_Staka-yo · August 4, 2013, 3:36am

Issue #8716 has been updated by nobu (Nobuyoshi N.).

Description updated
Assignee set to k_takata (Ken Takata)

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi (taka-yoshi taka)
Status: Assigned
Priority: Normal
Assignee: k_takata (Ken Takata)
Category: regexp
Target version: current: 2.1.0
ruby -v: trunk
Backport:

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · August 18, 2013, 12:30pm

Issue #8716 has been updated by k_takata (Ken Takata).

採用予定のパッチです。
fix: segmation fault occurs when many groups are used (Close #24) · k-takata/Onigmo@b9fba1d · GitHub
Windowsで落ちなくなったことは確認しましたが、それ以外の環境は未確認です。

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi (taka-yoshi taka)
Status: Assigned
Priority: Normal
Assignee: k_takata (Ken Takata)
Category: regexp
Target version: current: 2.1.0
ruby -v: trunk
Backport:

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · January 30, 2014, 7:26am

Issue #8716 has been updated by Hiroshi SHIBATA.

Target version changed from 2.1.0 to current: 2.2.0

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi taka
Status: Assigned
Priority: Normal
Assignee: Ken Takata
Category: regexp
Target version: current: 2.2.0
ruby -v: trunk
Backport:

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · March 8, 2014, 11:07am

Issue #8716 has been updated by Ken Takata.

Rubyにはおそらく影響しないのですが、上記リンク先を見ていただければ分かるとおり、
マルチスレッド環境でこの変更がうまく動かない場合があるようなので、修正方法を再度検討中です。

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi taka
Status: Assigned
Priority: Normal
Assignee: Ken Takata
Category: regexp
Target version: current: 2.2.0
ruby -v: trunk
Backport:

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · April 19, 2014, 8:49am

Issue #8716 has been updated by Ken Takata.

キャプチャグループの数を ONIG_MAX_CAPTURE_GROUP_NUM (32767) 個に制限することにしました。
それに合わせて、ONIGERR_TOO_MANY_CAPTURE_GROUPS というエラーコードを新設することにしました。

tmp/ruby-2.0.x ブランチも更新済みです。 # ブランチ名をそろそろどうにかすべきかも

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi taka
Status: Assigned
Priority: Normal
Assignee: Ken Takata
Category: regexp
Target version: current: 2.2.0
ruby -v: trunk
Backport:

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · April 16, 2014, 12:28pm

Issue #8716 has been updated by Ken Takata.

落ちる原因が2つあることが分かりました。

alloca でスタックオーバーフロー
(修正済み)
そもそも鬼雲（鬼車も）は、グループの数を short
で管理しているため、32767個以上のグループを管理できない。32768個あるとインデックスが負になり、不正アクセスが発生。(未修正)

グループの数を 32bit で管理するようにするか、それとも 16bit
のままとし、不正アクセスが発生しないように何らかのチェックを入れるか検討が必要です。

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi taka
Status: Assigned
Priority: Normal
Assignee: Ken Takata
Category: regexp
Target version: current: 2.2.0
ruby -v: trunk
Backport:

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · July 17, 2014, 12:12am

Issue #8716 has been updated by Ken Takata.

Assignee changed from Ken Takata to Yui NARUSE

r46831 で Onigmo 5.14.1 がマージされましたので、これも取り込まれました。
チケットのクローズ手順がよく分かっていないので、処理をお願いします。＞NARUSEさん
(あと #9344 も)

Ruby 2.0/2.1へのバックポートはどうしましょうか。

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi taka
Status: Assigned
Priority: Normal
Assignee: Yui NARUSE
Category: regexp
Target version: current: 2.2.0
ruby -v: trunk
Backport:

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · July 17, 2014, 9:35am

Issue #8716 has been updated by Shota F…

Status changed from Assigned to Closed

閉じます

Edit → Status → Closed ですね。あるいは ChangeLog/commitMessage で [Bug #8716]
とか。

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi taka
Status: Closed
Priority: Normal
Assignee: Yui NARUSE
Category: regexp
Target version: current: 2.2.0
ruby -v: trunk
Backport:

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · July 17, 2014, 9:51am

Issue #8716 has been updated by Usaku NAKAMURA.

Backport set to 2.0.0: REQUIRED, 2.1: REQUIRED

Ken Takata wrote:

Ruby 2.0/2.1へのバックポートはどうしましょうか。

該当修正部分のみを抽出して取り込むことになるかと思います。

しかし、backportチケットから持ってくるとBackport欄が空白になるというのは
本当に困るのでどうにかならないものかしらん？

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi taka
Status: Closed
Priority: Normal
Assignee: Yui NARUSE
Category: regexp
Target version: current: 2.2.0
ruby -v: trunk
Backport: 2.0.0: REQUIRED, 2.1: REQUIRED

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · July 17, 2014, 11:09am

Issue #8716 has been updated by Ken Takata.

クローズの際の取り決めがあるのかということを気にしていました。
(勝手に閉じて良いのかとか、Backport 欄は誰が何を設定するとか。)

該当修正部分のみを抽出して取り込むことになるかと思います。

関連コミットを挙げておきます。以下の4件となります。

alloca でスタックオーバーフロー
fix: segmation fault occurs when many groups are used (Close #24) · k-takata/Onigmo@b9fba1d · GitHub
fix memory leaks · k-takata/Onigmo@c1fc76b · GitHub
additional fix for #24 · k-takata/Onigmo@a0efc0a · GitHub
キャプチャグループの数を ONIG_MAX_CAPTURE_GROUP_NUM (32767) 個に制限
[bug] add checking the number of capture groups (fix #24) · k-takata/Onigmo@c7cda4e · GitHub

1.9.3 もバックポート対象とした方が良いかもしれません。（が、コンフリクトが発生するはず。）

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi taka
Status: Closed
Priority: Normal
Assignee: Yui NARUSE
Category: regexp
Target version: current: 2.2.0
ruby -v: trunk
Backport: 2.0.0: REQUIRED, 2.1: REQUIRED

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · August 19, 2014, 5:52pm

Issue #8716 has been updated by Tomoyuki C…

Backport changed from 2.0.0: REQUIRED, 2.1: REQUIRED to 2.0.0: REQUIRED,
2.1: DONE

r47223 で ruby_2_1 ブランチに r46831 から抽出して頂いた関連コミットの部分をバックポートしました。
関連する変更点を提示して頂いて大変助かりました、ありがとうございます。

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi taka
Status: Closed
Priority: Normal
Assignee: Yui NARUSE
Category: regexp
Target version: current: 2.2.0
ruby -v: trunk
Backport: 2.0.0: REQUIRED, 2.1: DONE

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · September 5, 2014, 6:43am

Issue #8716 has been updated by Usaku NAKAMURA.

Backport changed from 2.0.0: REQUIRED, 2.1: DONE to 2.0.0: DONE, 2.1:
DONE

遅ればせながら ruby_2_0_0 にも取り込みました。ありがとうございます。

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi taka
Status: Closed
Priority: Normal
Assignee: Yui NARUSE
Category: regexp
Target version: current: 2.2.0
ruby -v: trunk
Backport: 2.0.0: DONE, 2.1: DONE

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

taka-yoshi_Staka-yo · July 17, 2014, 11:17am

Issue #8716 has been updated by Usaku NAKAMURA.

Ken Takata wrote:

クローズの際の取り決めがあるのかということを気にしていました。
(勝手に閉じて良いのかとか、Backport 欄は誰が何を設定するとか。)

直したら閉じていいですし、直ってるのに閉じてなかったら閉じていいです。
……というくらいのゆるーい運用だと思います、現状は。
あまり厳密なルール作ってもどうせ守られないので、こんなもんでよろしいかと。

Backport欄はUNKNOWNで放置するのが安全です。
それなりの確信があればREQUIREDやDONTNEEDにしてもかまいません。
削除だけは大変に困るので避けていただけると幸いです。

該当修正部分のみを抽出して取り込むことになるかと思います。
関連コミットを挙げておきます。以下の4件となります。

ありがとうございます。助かります。

1.9.3 もバックポート対象とした方が良いかもしれません。（が、コンフリクトが発生するはず。）

1.9.3は通常メンテナンスフェーズを終えているので、セキュリティイシューしか取り扱いません。

Bug #8716: segmation fault 正規表現で大量のグループを利用時

Author: taka-yoshi taka
Status: Closed
Priority: Normal
Assignee: Yui NARUSE
Category: regexp
Target version: current: 2.2.0
ruby -v: trunk
Backport: 2.0.0: REQUIRED, 2.1: REQUIRED

=begin
WindowsとOS Xで検証しました。
*再現手順 ruby 2.0.0p247 (2013-06-27) [x64-mingw32]
a=“()”
(32767.times{a<<‘()’}
eval “/#{a}/=~‘’”

*再現手順 ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin12.2.1]
a=“()”
(1<<21).times{a<<‘()’}
eval “/#{a}/=~‘’”

以上よろしくお願いします。
=end

regexec.c:match_at()で呼ばれるSTACK_INITがサイズを考慮せずにxallocaしているため、スタックオーバーフローしています。

採用予定のパッチです。 fix: segmation fault occurs when many groups are used (Close #24) · k-takata/Onigmo@b9fba1d · GitHub Windowsで落ちなくなったことは確認しましたが、それ以外の環境は未確認です。

採用予定のパッチです。
fix: segmation fault occurs when many groups are used (Close #24) · k-takata/Onigmo@b9fba1d · GitHub
Windowsで落ちなくなったことは確認しましたが、それ以外の環境は未確認です。