n4o847 commented 3 years ago

まだ正しく動作しないためマージしないでください

18 で指摘いただいたように遷移関数と文字の定義を変更するものです。

手をつけられそうなところから移行していますが、変更が大きいため、ふたりにもしっかりめに確認してもらいたいと思っています。

特に SCC と 3直積は自信が無いです。各自が書いた部分の移行は結構手伝ってほしいところがあります。

主な変更点は以下です。

各時点でのオートマトンについて、alphabet: Set<Char> を持つことを強制します。Char は #18 で言われた通りの文字です。まだわかりませんが場合によっては alphabet: Char[] になるかもしれません。どちらにせよ alphabet の列挙によってアルゴリズムが改善できる点があれば変更お願いします。
NonEpsilonNFA 移行のオートマトンについて、遷移関数を transitions: TransitionMap に変更します。TransitionMap は独自に定義したクラスで、内部的には Map<State, Map<Char, State>> と同じですが、各変換で初期化処理や列挙が面倒になっていることから、共通化したほうが見通しが良いと考えクラスにしました。下手にクラスを持たないほうがいいということであれば変更も考えます。

移行がつらいようであれば、時間も厳しいですし断念するかもしれません。

n4o847 commented 3 years ago

TransitionMap は最初に初期化するより遅延的に処理したほうがいいか

masa5555 commented 3 years ago

反応遅くて申し訳ないです。一つ気づいたんですが、DirectProductNFAやTripleDirectProductNFAという名前になってしまっています

n4o847 commented 3 years ago

あれ、ソースコード内でですか？　どの辺でしょう、、、

n4o847 commented 3 years ago

動くには動きましたが、master ブランチの出力と diff とったら

a* EDA false positive
a*? EDA false positve
(.*)="(.*)" EDA false positive
[a-z][0-9a-z]* EDA false positive
a*a* EDA false positive
a*a* IDA false negative

みたいな感じでしんどい………… (SCC とかがちゃんとできてない気がする)

masa5555 commented 3 years ago

あれ、ソースコード内でですか？　どの辺でしょう、、、

ごめんなさい。見間違えでした。StronglyConectedComponentNFAの方でした。

動くには動きましたが、master ブランチの出力と diff とったら

a* EDA false positive

a*? EDA false positve

(.*)="(.*)" EDA false positive

[a-z][0-9a-z]* EDA false positive

a*a* EDA false positive

a*a* IDA false negative

みたいな感じでしんどい………… (SCC とかがちゃんとできてない気がする)

途中経過見てみます

masa5555 commented 3 years ago

前の命名変更プルリクのときにやるべきだったんですが、dpNFA, tdpNFAだけでなく、SCCNFAという名前も変える必要があることに気づきました。（まあこれは後で良いかも知れませんが）

n4o847 commented 3 years ago

あとは

(a|b)* EDA false negative
(.*)="(.*)" IDA false ~negative~ positive

になりました

n4o847 commented 3 years ago

あれ、よく考えたら /^(a|b)*$/ って Safe ですね（https://makenowjust-labo.github.io/redos/ で試してもそうなる）

もとの検出が間違っていたんでしょうか

n4o847 commented 3 years ago

確認したところ、

master のときに EDA Vulnerable だった (a|b)* が Safe になった
master のときに IDA Safe だった (.*)="(.*)" が Vulnerable になった

ので、むしろ今までより改善されていることがわかりました！！

引き続き、他の例でも試してみるなり、コードの変更部分のチェック（特にもともとその部分を書いていた人）はお願いします。

（めちゃくちゃ変えてしまったところもあるので、気に食わないところがあったら変えちゃってください）

n4o847 commented 3 years ago

前の命名変更プルリクのときにやるべきだったんですが、dpNFA, tdpNFAだけでなく、SCCNFAという名前も変える必要があることに気づきました。（まあこれは後で良いかも知れませんが）

これもなんなら今変えちゃっていいと思います（ちっちゃい変更だとプルリク出すの面倒だと思うので……）

masa5555 commented 3 years ago

前の命名変更プルリクのときにやるべきだったんですが、dpNFA, tdpNFAだけでなく、SCCNFAという名前も変える必要があることに気づきました。（まあこれは後で良いかも知れませんが）

これもなんなら今変えちゃっていいと思います（ちっちゃい変更だとプルリク出すの面倒だと思うので……）

では自分やります

yapatta commented 3 years ago

すみません返信が遅れました、明日の昼ごろに一通りコード読みます、ご了承下さい

n4o847 commented 3 years ago

すみません返信が遅れました、明日の昼ごろに一通りコード読みます、ご了承下さい

ぜんぜん大丈夫です、ありがとうございます～（そもそも、全員が常にすぐ反応できることを前提にはできないですしね）

makenowjust commented 3 years ago

TrpleDirectProductGraphの構築のアルゴリズムを読んでも何をやっているのかよく分からないのですが、何かしら間違っている気がします。今の書き方を尊重するのであれば、次のようになるはずです。 (createState で存在しない場合に新しい状態を生成して追加するようにすればもっとシンプルになるんじゃないでしょうか)

  build(): TripleDirectProductGraph {
    // sccGraph1 で lq --char-->ld、
    // 元のnfaで cq --char-->cd、
    // sccGraph2で rq --char--> rd という辺がある場合に、
    // (lq, cq, rq) ---char--> (ld, cd, rd) という辺を追加
    for (const lq of this.sccGraph1.stateList) {
      for (const cq of this.nfa.stateList) {
        for (const rq of this.sccGraph2.stateList) {
          for (const char of this.nfa.alphabet) {
            for (const ld of sumOfTwoSccTransitions.get(lq, char)) {
              for (const cd of sumOfTwoSccTransitions.get(cq, char)) {
                for (const rd of sumOfTwoSccTransitions.get(rq, char)) {
                  let source = this.getState(lq, cq, rq);
                  if (source === null) {
                    source = this.createState(lq, cq, rq);
                  }

                  let dest = this.getState(ld, cd, rd);
                  if (dest === null) {
                    dest = this.createState(ld, cd, rd);
                  }

                  this.newTransitions.add(source, char, dest);
                }
              }
            }
          }
        }
      }
    }

    // IDA判定のために、強連結成分間の戻る辺を追加
    for (const lq of this.sccGraph1.stateList) {
      for (const rq of this.sccGraph2.stateList) {
        let source = this.getState(lq, rq, rq);
        if (source === null) {
          source = this.createState(lq, rq, re);
        }

        let dest = this.getState(lq, lq, rq);
        if (dest === null) {
          dest = this.createState(lq, lq, re);
        }

        // 'back' をIDA判別のために追加した辺のラベルということにする
        this.newTransition(source, 'back', dest);
      }
    }

    return {
      type: 'TripleDirectProductGraph',
      stateList: this.newStateList,
      alphabet,
      transitions: this.newTransitions,
      extraTransitions: this.extraTransitions,
    };
  }

それと、IDA検出の際に extraTransition を使って判定していますが、強連結成分の stateList に lq, lq, rq 相当の頂点と lq, rq, rq 相当の頂点の両方が存在するかを確認すればいいはずです。

function isIDA(tdp: TripleDirectProductGraph): boolean {
  const sccs = buildStronglyConnectedComponents(tdp);
  return sccs.some((scc) => {
    // (lq, lq, rq) と (lq, rq, rq) が存在するかを確認する。
    for (const [lq, cq, rq] of scc.stateList.map(s => s.split('_'))) {
      if (lq === cq && scc.stateList.includes(`${lq}_${rq}_${rq}`)) {
        return true;
      }
    }
    return false;
  });

n4o847 commented 3 years ago

レビューありがとうございます。

上の変更については余裕があれば @masa5555 さんお願いできますか？

State の扱いはまた全体で改善すべきことなので別の問題として話し合いたいと思います。

yapatta commented 3 years ago

charの遷移の変更書いてくださりありがとうございます、本当にお疲れ様でした、と同時に返信が遅れてしまい申し訳ありません。書き方がきれいで学びが多いコードでした！(直積とEDAの方も変更いい感じだと思います, tripleの方は見ておりません) ではでは気になった点なのですが、

外部関数extendAlphabetでthis.alphabetを参照で更新しているのがわかりにくかった(バグを生みかねない) => EpsilonNFABuilder内のメンバ関数としてextendAlphabetを定義したほうが良さそう. enfa用にしか使わないし(オートマトンに出現する文字を構成するのはenfa構成の最初の一回で良い)
Viz表示でエラーが生じる(ex: \s)

もしよろしければ自分の方で編集して直しておきます。逆に自分が提案した修正について良からぬことがありそうな場合伝えてくれるとありがたいです。

n4o847 commented 3 years ago

ありがとうございます！

確かに文字構築の処理はちょっとまだ苦しいところがあります。指摘部分はそのとおりで、場所を変えた方が適切かもしれないです。

\s はそうか、 unescape もう一回しないといけないんですね、、、。

編集してもらえるとありがたいです、お願いします。

yapatta commented 3 years ago

extendAlphabetをenfaに移すとrerejsのCharに関する処理をenfaでやらないと行けなくなってそれもそれで気持ち悪いな(Char関連をめちゃくちゃimportしないといけない...) こんな感じでメンバ関数に隠蔽して、char.tsのextendAlphabetを呼び出していることでお気持ちthis.alphabetを更新しているよと伝えるぐらいが丁度いい気がしてきた...(ここに時間を割くのも違う気がしてきたし)

  private extendAlphabet(node: Atom): void {
    // NOTE: 計算量が一番少ないthis.alphabetの更新方法
    extendAlphabet(this.alphabet, node, this.pattern.flagSet);
  }

n4o847 commented 3 years ago

うーん難しいですね（どちらも気持ちはわかる）

それでもいいと思いますし、任せます（そうするとついでに getChars もですね）

yapatta commented 3 years ago

これViz表示JSON.Stringfyでエスケープ文字を文字列に変換しているのを気づかずに, d.charについてエスケープされるアスキーコードの範囲で場合分けされるみたいな処理を書こうとしてしまった... JSON.Stringfyで変換された文字にバックスラッシュが含まれる場合2個に置換するだけだった getChars, extendAlphabet両方にやっておきました(getCharsは副作用はないがラップしたほうが自然だった). あとそろそろ枝切りに取り組みます、このブランチから派生させようかな

n4o847 commented 3 years ago

あ、unescape じゃなくて escape だ……まあどっちでもいいです

自分も攻撃文字列の生成をこのブランチから派生させます

（State の変換周辺も直したいのもやまやまですが、うーむ……）

yapatta commented 3 years ago

了解です〜 Stateの件すごくわかります....(文字列分解でやるとしたらdirectProductのnewStateToOldStateSetいらねえな...)

yapatta commented 3 years ago

今問題なのって(というかこのブランチをマージしていない理由)

TrpleDirectProductGraphのIDA検出
Stateの扱い

ぐらいの認識なので、もしかしたらこのブランチマージしてもいいかもしれませんね(恐らく昔のCharSet利用に戻ることはない気がするので)

n4o847 commented 3 years ago

かもですね、現状今までより悪化している点は無いはずです。

@masa5555 IDA検出が変更できたら、またプルリク建ててもらって良いでしょうか？

masa5555 commented 3 years ago

了解です。指摘いただいた点の冗長な表現は削除できたのですが、元々(.*)=(.*)の検出が上手く行っていないので、アルゴリズムの見直しをしています

n4o847 / seccamp-redos

[WIP]遷移関数と文字の定義の変更 (#18) #21

18 で指摘いただいたように遷移関数と文字の定義を変更するものです。