文献

J-GLOBAL ID：202002230259013815   整理番号：20A0258907

SATソルバによるルールリストポリシの等価判定

Deciding Equivalence of The Rule List Policies via SAT solver

著者 (4件)： 渕野敬 (神奈川大 大学院理学研究科) ,  原田崇司 (高知工科大 情報学群) ,  田中賢 (神奈川大 大学院理学研究科) ,  三河賢治 (新潟大 学術情報基盤機構 情報基盤セ)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 119  号： 329(SITE2019 80-87)  ページ： 13-19  発行年： 2019年11月29日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： パケット分類とは,ネットワーク機器に到着するパケットの振る舞いをポリシに対応するルールリストによって決定することである.線形探索などによるパケット分類では,パケットとルールとの比較回数が増加するとパケット分類による通信の遅延が生じる.この遅延を減少させるために,ルールを並び替えたり,ルールリストを再構築する手法が考えられてきた.そのようにして生成されたルールリストは,元のルールリストと同じポリシを満たさなければならないが,それを判定する問題はcoNP完全である.本稿では,ルールリストに対応する論理式を構築し,SATソルバを用いたルールリスト等価判定法を提案する.一方で,ルールを並び替えることによってルールに合致するパケットが異なる場合がある.本稿では,ZDDを用いることで並び替えによって変動するルールの重みを厳密に求める手法を提案する.(著者抄録)

シソーラス用語： *NP完全問題 ,  二分決定グラフ ,  *発見的方法 ,  充足可能性問題 ,  応用プログラム ,  等価性 ,  *パケット ,  規則
準シソーラス用語： IPパケット ,  NP完全 ,  *ZDD ,  ソルバ ,  *パケット分類 ,  計算機実験 ,  決定リスト ,  決定ルール ,  判定問題 ,  分類モデル

分類 (2件)： 計算機網  (JC03000K) ,  計算理論  (JB02000A)

引用文献 (14件)：

• E.W. Fulp, ′′Optimization of network firewall poli-cies using directed acyclic graphs,′′ In Proc. IEEE Internet Management Conf, extended abstract, 2005. http://csweb.cs.wfu.edu/ fulp/wefPub.html
• G. Misherghi, L. Yuan, Z. Su, C.N. Chuah, and H. Chen, ′′A general framework for benchmarking firewall optimiza-tion techniques,′′ IEEE Transactions on Network and Ser-vice Management, vol.5, no.4, pp.227-238, Dec. 2008.
• A. Tapdiya and E.W. Fulp, ′′Towards optimal firewall rule ordering utilizing directed acyclical graphs,′′ Computer Communications and Networks, 2009. ICCCN 2009. Pro-ceedings of 18th Internatonal Conference on, pp.1-6, Aug. 2009.
• K. Tanaka, K. Mikawa, and K. Takeyama, ′′Optimization of packet filter with maintenance of rule dependencies,′′ IEICE Communications Express, vol.2, no.2, pp.80-85, Feb. 2013. http://ci.nii.ac.jp/naid/130003379292/en/
• 日景喬一,山田敏規,′′D-1-6 ルール間の依存関係を保持したファイアウォールの負荷最小化のためのアルゴリズム(d-1.コンピュテーション,一般セッション),′′電子情報通信学会総合大会講演論文集,vol.2016, no.1, p.6, mar 2016. http://ci.nii.ac.jp/naid/110010036640/

タイトルに関連する用語 (3件)： SAT ,  ソルバ ,  等価