脆弱な正規表現の自動修正技術に関する考察

• Item type: Symposium(1)
• 公開日: 2022-10-17
• タイトル: 脆弱な正規表現の自動修正技術に関する考察
• タイトル / 言語: en
• タイトル: On Automatic Repairs of Vulnerable Regular Expressions
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 脆弱性自動修正，Programming By Examples，正規表現，ReDoS
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: NTT セキュリティ・ジャパン
• 著者所属: 日本電信電話株式会社
• 著者所属(英): en
• 著者所属(英): NTT Security Japan
• 著者所属(英): en
• 著者所属(英): Nippon Telegraph and Telephone Corporation
• 著者名: 千田, 忠賢; 山口, 大輔
• 著者名(英): Nariyoshi, Chida; Daisuke, Yamaguchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 正規表現エンジンを対象とした DoS 攻撃 (Regular Expression Denial of Service, ReDoS) は正規表現エンジンの振る舞いを悪用し正規表現エンジンを DoS 状態に陥らせる攻撃である．正規表現エンジンは実世界で広く利用されていることから重大な脅威として認識されている．この状況を改善するため既存研究では ReDoS に対して脆弱な正規表現を自動で修正する技術を考案しているが，これらの技術では修正結果を見つけるために幅優先探索を採用しており修正結果の候補を列挙し続けることでしばしば膨大な量のメモリを消費する．本論文では反復深化深さ優先探索を用いた修正アルゴリズムを提案する．反復深化深さ優先探索を用いることで探索中に保持すべき修正結果の候補が探索による再帰の深さ程度に限定される．これにより幅優先探索の場合と比べ探索中に保持すべき修正結果の候補の量が削減され，より少ないメモリ使用量での修正できるようになることが期待できる．評価では実世界の脆弱な正規表現を用い，既存研究との比較によりこれらを実験的に確かめる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Regular expression denial of service~(ReDoS) attacks are DoS attacks that exploit the behavior of regular expression engines and lead the running time of regular expression engines into a stalling or DoS state. Due to the widespread use of regular expression engines in practice, ReDoS attacks are a significant threat to our society. To rectify this situation, existing work has studied an automatic repair method of regular expressions that are vulnerable to ReDoS attacks. The automatic repair method is based on breadth-first search~(BFS) and therefore it may generate and store a lot of candidates for the repair. From this, the BFS-based repair method may consume a lot of memory to store the candidates. In this paper, we introduce an automatic repair based on iterative deepening depth-first search~(IDDFS). In the case of IDDFS-based repair, the number of candidates for a repair is at most the depth of the recursion by the search. From this, we expect that the change of the search strategy positively affects the memory consumption. We conducted a comparison of the BFS-based and IDDFS-based repair methods and confirmed how the change of the search strategy affects the memory consumption.
• 書誌情報: コンピュータセキュリティシンポジウム2022論文集; p. 1113-1120, 発行日 2022-10-17
• 出版者 / 言語: ja
• 出版者: 情報処理学会