基于多选项二次联合背包的态势感知资源分配算法
Resource allocation algorithm for situation awareness based on multiple-choice quadratic knapsack
- 通信学报 2016年37卷第12期 页码：56-66
- 作者机构：
1. 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093
2. 东莞电子科技大学电子信息工程研究院，广东 东莞 523808
- 作者简介：
[ "孙岩炜（1989-），男，山西太原人，中国科学院信息工程研究所博士生，主要研究方向为网络安全。" ]
[ "郭云川（1977-），男，四川营山人，博士，中国科学院信息工程研究所副研究员，主要研究方向为网络与信息系统安全、访问控制。" ]
[ "张玲翠（1986-），女，河北故城人，中国科学院信息工程研究所博士生，主要研究方向为网络安全、信息保护。" ]
[ "方滨兴（1960-），男，江西万年人，中国工程院院士，东莞电子科技大学教授，主要研究方向为计算机体系结构、计算机网络与信息安全。" ]
- 基金信息：中国科学院战略性科技先导专项基金资助项目(XDA06030200);国家重点研发计划基金资助项目(2016YFB0800303);国家重点研发计划基金资助项目(2016YFB0800700);国家“核高基”基金资助项目(2015ZX01029101);广东省产学研合作基金资助项目(2016B090921001)
DOI：10.11959/j.issn.1000-436x.2016272
中图分类号： TP301-
网络首发：2016-12，
纸质出版：2016-12-25
- 稿件说明：
移动端阅览
孙岩炜, 郭云川, 张玲翠, 等. 基于多选项二次联合背包的态势感知资源分配算法[J]. 通信学报, 2016,37(12):56-66.
Yan-wei SUN, Yun-chuan GUO, Ling-cui ZHANG, et al. Resource allocation algorithm for situation awareness based on multiple-choice quadratic knapsack[J]. Journal on Communications, 2016, 37(12): 56-66.
孙岩炜, 郭云川, 张玲翠, 等. 基于多选项二次联合背包的态势感知资源分配算法[J]. 通信学报, 2016,37(12):56-66. DOI： 10.11959/j.issn.1000-436x.2016272.
Yan-wei SUN, Yun-chuan GUO, Ling-cui ZHANG, et al. Resource allocation algorithm for situation awareness based on multiple-choice quadratic knapsack[J]. Journal on Communications, 2016, 37(12): 56-66. DOI： 10.11959/j.issn.1000-436x.2016272.
摘要
为了有效应对潜在网络威胁，通过合理利用资源达到最大化提升当前环境安全态势的目的，研究了有限资源的最优分配方案。网络态势的整体性特点使针对某一指标的改善可能会间接影响其他指标，并且投入力度不同，影响程度也有所差异。针对上述特性，将问题抽象成多选项二次联合背包模型，通过二次背包特性表示态势评估指标项之间的相互影响，通过多选项背包特性来表示单个指标项的多种投入可能。最后对其做半定规划松弛，采用分支定界法对问题进行求解。实验证明了算法的准确性和高效性。
Abstract
In order to deal with the potential cyber-threat and improve the security situation by using limited resource properly
the optimal allocation of resource focused on cyber security situation. The coherence of network situation lead to the fact that the enhancement of certain item may also affect some other items
and different amount of investment may also result in different degree of impact
therefore
the problem was extracted into the multiple-choice quadratic knapsack problem. The characteristics of quadratic knapsack problem was used to model the interactions among the situation indi-cator items
meanwhile used the multiple choice knapsack problem to model the multiple investment choice for each item. A branch and bound algorithm was conducted by using the semi-definite relaxation. The experiment results show the ac-curacy and efficiency of proposed algorithm.
关键词
Keywords
references
ENDSLEY M R . Toward a theory of situation awareness in dynamic systems [J ] . Human Factors: The Journal of the Human Factors and Ergonomics Society , 1995 , 37 ( 1 ): 32 - 64 .
DIETTERICH T G , BAO X , KEISER V , et al . Machine learning methods for high level cyber situation awareness [M ] // Cyber Situ-ational Awareness . Springer US , 2010 : 227 - 247 .
LIU P , JIA X , ZHANG S , et al . Cross-layer damage assessment for cyber situational awareness [J ] . Advances in Information Security , 2010 , 46 : 155 - 176 .
PREDEN J , MOTUS L , MERISTE M , et al . Situation awareness for networked systems [C ] // 2011 IEEE International Multi-Disciplinary Conference on Cognitive Methods in Situation Awareness and Deci-sion Support (CogSIMA). IEEE . 2011 : 123 - 130 .
BRANNON N G , SEIFFERTT J E , DRAELOS T J , et al . Coordinated machine learning and decision support for situation awareness [J ] . Neural Networks , 2009 , 22 ( 3 ): 316 - 325 .
TAMASSIA R , PALAZZI B , PAPAMANTHOU C . Graph drawing for security visualization [C ] // International Symposium on Graph Drawing. Springer Berlin Heidelberg , 2008 : 2 - 13 .
TADDA G P , SALERNO J S . Overview of cyber situation aware-ness [M ] . Cyber Situational Awareness . Springer US , 2010 : 15 - 35 .
WEBB J , AHMAD A , MAYNARD S B , et al . A situation awareness model for information security risk management [J ] . Computers ＆ Se-curity , 2014 , 44 : 1 - 15 .
Federal Office for Information Security: 13 EL: Cross-reference tables of the IT-grundschutz catalogues: 13th version (2013) [EB/OL ] . https://http://enos.itcollege.ee/～valdo/bsieng/en/gstoolhtml/allgemein/vorwort/00001.html https://http://enos.itcollege.ee/～valdo/bsieng/en/gstoolhtml/allgemein/vorwort/00001.html .
GREITZER F L , FRINCKE D A . Combining traditional cyber security audit data with psychosocial data: towards predictive modeling for in-sider threat mitigation [M ] // Insider Threats in Cyber Security . Springer US , 2010 : 85 - 113 .
SCHILLING A , WERNERS B . Optimizing information systems secu-rity design based on existing security knowledge [C ] // International Conference on Advanced Information Systems Engineering . Springer International Publishing , 2015 : 447 - 458 .
DU J , COOK W D , LIANG L , et al . Fixed cost and resource allocation based on DEA cross-efficiency [J ] . European Journal of Operational Research , 2014 , 235 ( 1 ): 206 - 214 .
AISOPOS F , TSERPES K , VARVARIGOU T . Resource management in software as a service using the knapsack problem model [J ] . Interna-tional Journal of Production Economics , 2013 , 141 ( 2 ): 465 - 477 .
XIAO Z , SONG W , CHEN Q . Dynamic resource allocation using virtual machines for cloud computing environment [J ] . IEEE Transac-tions on Parallel and Distributed Systems , 2013 , 24 ( 6 ): 1107 - 1117 .
HAJIAGHAJANI F , RASTI M . Downlink resource reuse for de-vice-to-device communication underlying cellular networks using a generalized knapsack framework [C ] // 2016 13th IEEE Annual Con-sumer Communications ＆ Networking Conference (CCNC). IEEE , 2016 : 171 - 176 .
FERDOSIAN N , OTHMAN M , ALI B M , et al . Greedy–knapsack algorithm for optimal downlink resource allocation in LTE networks [J ] . Wireless Networks , 2015 : 1 - 14 .
SHEU J P , KAO C C , YANG S R , et al . A resource allocation scheme for scalable video multicast in WiMAX relay networks [J ] . IEEE Transactions on Mobile Computing , 2013 , 12 ( 1 ): 90 - 104 .
FIELDER A , PANAOUSIS E , MALACARIA P , et al . Decision sup-port approaches for cyber security investment [J ] . Decision Support Systems , 2016 , 86 : 13 - 23 .
KHOUZANI M H R , MALACARIA P , HANKIN C , et al . Efficient numerical frameworks for multi-objective cyber security plan-ning [C ] // European Symposium on Research in Computer Security . Springer International Publishing , 2016 : 179 - 197 .
OJAMAA A , TYUGU E , KIVIMAA J . Pareto-optimal situation analy-sis for selection of security measures [C ] // MILCOM 2008-2008 IEEE Military Communications Conference. IEEE , 2008 : 1 - 7 .
WANG F , XU C , SONG L , et al . Energy-efficient resource allocation for device-to-device underlay communication [J ] . IEEE Transactions on Wireless Communications14.4 . 2015 : 2082 - 2092 .
HASAN M , HOSSAIN E . Distributed resource allocation in D2D-enabled multi-tier cellular networks: an auction approach [C ] // 2015 IEEE International Conference on Communications (ICC). IEEE , 2015 .
ZHANG H , JIANG H , LI B , et al . A framework for truthful online auctions in cloud computing with heterogeneous user demands [J ] . IEEE Transactions on Computers , 2016 , 65 ( 3 ): 805 - 818 .
GUPTA M , REES J , CHATURVEDI A , et al . Matching information security vulnerabilities to organizational security profiles: a genetic algorithm approach [J ] . Decision Support Systems , 2006 , 41 ( 3 ): 592 - 603 .
VIDUTO V , MAPLE C , HUANG W , et al . A novel risk assessment and optimization model for a multi-objective network security coun-termeasure selection problem [J ] . Decision Support Systems , 2012 , 53 ( 3 ): 599 - 610 .
REES L P , DEANE J K , RAKES T R , et al . Decision support for cyber security risk planning [J ] . Decision Support Systems , 2011 , 51 ( 3 ): 493 - 505 .
SAWIK T . Selection of optimal countermeasure portfolio in IT secu-rity planning [J ] . Decision Support Systems , 2013 , 55 ( 1 ): 156 - 164 .
MUKHOPADHYAY A , CHATTERJEE S , SAHA D , et al . Cyber-risk decision models: to insure IT or not? [J ] . Decision Support Systems , 2013 , 56 : 11 - 26 .
GORDON L A , LOEB M P . The economics of information security investment [M ] // Economics of Information Security . Springer US , 2004 : 105 - 125 .
LÉTOCART L , PLATEAU M C , PLATEAU G . An efficient hybrid heuristic method for the 0-1 exact k-item quadratic knapsack prob-lem [J ] . Pesquisa Operacional , 2014 , 34 ( 1 ): 49 - 72 .
SHENG H , SUN J , SUN X . A Rigorous method for solving 0-1 poly-nomial knapsack problem [J ] . Journal of Shanghai University (Natural Science Edition) , 2006 , 4 : 012 .
BRETTHAUER K M , SHETTY B . Quadratic resource allocation with generalized upper bounds [J ] . Operations Research Letters , 1997 , 20 ( 2 ): 51 - 57 .
HAHN P , GRANT T . Lower bounds for the quadratic assignment problem based upon a dual formulation [J ] . Operations Research , 1998 , 46 ( 6 ): 912 - 922 .
HAHN P M , KIM B J , GUIGNARD M , et al . An algorithm for the generalized quadratic assignment problem [J ] . Computational Optimi-zation and Applications , 2008 , 40 ( 3 ): 351 - 372 .
BILLIONNET A , ELLOUMI S , PLATEAU M C . Improving the per-formance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: the QCR method [J ] . Discrete Applied Mathe-matics , 2009 , 157 ( 6 ): 1185 - 1197 .
CAPRARA A , PISINGER D , TOTH P . Exact solution of the quadratic knapsack problem [J ] . Informs Journal on Computing , 1999 , 11 ( 2 ): 125 - 137 .
ANDERSON R H , FELDMAN P M , GERWEHR S , et al . Securing the US defense information infrastructure: a proposed approach [R ] . Rand Corp Santa Monica CA , 1999 .
KELLERER H , PFERSCHY U , PISINGER D . Introduction to NP-completeness of knapsack problems [M ] . Springer Berlin Heidel-berg , 2004 .
BRETTHAUER K M , SHETTY B . The nonlinear knapsack prob-lem–algorithms and applications [J ] . European Journal of Operational Research , 2002 , 138 ( 3 ): 459 - 472 .
0
浏览量
1405
下载量
0
CSCD
- 网络PDF下载
- XML下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
AI问答- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies
- 总访问量：582278 今日访问量：94