search

n4o847 / seccamp-redos

A tool for detecting ReDoS vulnerabilities based on automata theory.
https://n4o847.github.io/seccamp-redos/
7 stars 4 forks source link

枝切り実装 #25

Closed yapatta closed 3 years ago

yapatta commented 3 years ago

~~今現在枝切り実装が完了したが、もとのテストケースでEDA: positive、IDA: positiveのやつもfalseになってしまっている。 検証始めます。~~

すべてSafeになっているのまずいんだよなあ...

また三浦くんが作ったredefine_state_2の新規Stateをもとに実装しております。

枝切り検出可能に

例: (a|a)*?.*, (.*|(a|a)*

yapatta commented 3 years ago

q0からある文字charで一度でもどこかに遷移したらその他の遷移を考えなくなっちゃっているな。。。 目的のStateが違うときはちゃんと遷移しないといけない

yapatta commented 3 years ago

完全に同じ遷移じゃない限りは遷移を生やすことができるという制約を見逃していた TransitionMapクラスにhasメソッドを作って対応した(同じ辺は存在しても1つなので計算量的にlog(sourceの個数)×log(charの個数)になっているから問題もないはず)

yapatta commented 3 years ago

もとの検出と比較したところ残りは(a*)*と(a+)+に。 なんとなく二重辺壊しているような予感がする。 あと逆に新しく追加した(.*|(a|a)*)がVulnerableになってしまった。いやこれはVulnerableでいいのか？(https://makenowjust-labo.github.io/redos/だとunsafeに)

makenowjust commented 3 years ago

@yuziroppe /^(.*|(a|a)*)$/s だとsafeなはずです。(JavaScriptの正規表現の.はデフォルトでは改行文字を含まないため)

yapatta commented 3 years ago

残りのTODO(恐らく)

yapatta commented 3 years ago

枝刈りでEDA誤検知は防げたが、IDA positiveがSafeになるな... (.*)="(.*)とa*a*がIDA Safeになってしまう 他は以前と同じく正しく検知できている

yapatta commented 3 years ago

VIzでデバッグしたら完全理解した。3直積のグラフを作成するとき、一つ枝切りEDAではなくもとのEDAを入れていた

yapatta commented 3 years ago

枝刈り正しく検知するようになりました！ もしよろしければマージお願いします

n4o847 commented 3 years ago

うおおお疲れさまです！