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

状態のタプルを移行 (#22) #38

Closed n4o847 closed 3 years ago

n4o847 commented 3 years ago

22 の移行（State を q0_q1 ではなく (q0, q1) にする）を DirectProductGraph と TripleDirectProduct にも施したものです。

26 をやる上で必要になったので出しました。

（試しに提案されたブランチ名ルールを取り入れてみたけど、プッシュ先は master です）

n4o847 commented 3 years ago

build() しかないクラス、クラスである必要が無い説がある

yapatta commented 3 years ago

あとこの実装をマージしたあと、枝切りの方にもtableを付け加える必要がありそうですね

n4o847 commented 3 years ago

あとこの実装をマージしたあと、枝切りの方にもtableを付け加える必要がありそうですね

これたぶん攻撃文字列生成で必要そうなんですよね……

そのときにやるか、ここでやっちゃうか

yapatta commented 3 years ago

またプルリクを生やすのもめんどいですしここでやっちゃいましょうかね もしよろしければ、自分が枝切りのtable追加しておきます

n4o847 commented 3 years ago

あ、勘違いしていて、攻撃文字列に必要なのは強連結成分グラフの方でした

自分はそっちやるので、枝刈りの方お願いします！

yapatta commented 3 years ago

あ、勘違いしていて、攻撃文字列に必要なのは強連結成分グラフの方でした

なるほど、あれじゃあPrunedNFAには必ずしも, tableは必要ない？(自分が攻撃文字列判定のアルゴリズムを理解していない) とりあえずあまり重いタスクでもないのでPrunedNFAのtableは一応追加しておきます~

n4o847 commented 3 years ago

や、強連結成分が持たなくてもやる方法はあるか

強連結成分に table を持たせると何が面倒かというと、何を強連結成分分解したかによって table の型が変わるので型をゴリゴリしなければならず、だったら持たせない方に振ります……

枝刈りの方は具体的に何に必要かはまだわかりませんが可能ならお願いします

yapatta commented 3 years ago

強連結成分に table を持たせると何が面倒かというと、何を強連結成分分解したかによって table の型が変わるので型をゴリゴリしなければならず、だったら持たせない方に振ります……

今現在攻撃文字列作成のために, SCCでtableを用いてStateをもとのStateたちに分けてあげる必要があるが, SCCPossibleAutomatonは複数の型を持ちうるので, typeに応じてtableの処理を変えないと行けないという感じなんですかね てかまだWIPですが攻撃文字列作成で何をやっているか僕もちゃんと見たほうがいいですね(何が必要なのかわかっていない)