講演抄録/キーワード |
講演名 |
2022-10-26 17:00
リスト構築問題の計算困難性 ○原田崇司(高知工科大)・渕野 敬・田中 賢(神奈川大)・三河賢治(前橋工科大) COMP2022-20 |
抄録 |
(和) |
ネットワーク機器に到着するパケットやネットワーク機器から出ていくパケットをセキュリティーポリシーに従って分類することをパケット分類という.パケット分類は,ポリシーを反映するルールリストを線型探索することで実現される.ルールリストのルール数が増加すると線型探索によって生じる遅延が大きくなるため,ポリシーを実現する遅延最小ルールリストを求める最適化問題が定式化されている.本稿では,この最適化問題の判定問題版が NP 困難であることを,Min-DNF から帰着することによって証明する. |
(英) |
Packet classification is to classify packets arriving to or leaving from a network device according to the security policy. It is achived by linear search for the rule list representing the policy. Since as the number of rules in the rule list increases, the latency caused by the packet classification increases, an optimization problem which minimizes the latency holding the policy have been formulated. In this paper, we show that the decision version of this optimization problem is NP-hard by showing the reduction from Min-DNF. |
キーワード |
(和) |
パケット分類 / 決定リスト / 許可リスト / 最小論理和形 / NP 困難 / / / |
(英) |
packet classification / decision list / allowlist / minimum sum-of-products expression / NP-hard / / / |
文献情報 |
信学技報, vol. 122, no. 229, COMP2022-20, pp. 32-37, 2022年10月. |
資料番号 |
COMP2022-20 |
発行日 |
2022-10-19 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2022-20 |