基于多选项二次联合背包的态势感知资源分配算法

doi:10.11959/j.issn.1000-436x.2016272

摘要/Abstract

摘要：

为了有效应对潜在网络威胁，通过合理利用资源达到最大化提升当前环境安全态势的目的，研究了有限资源的最优分配方案。网络态势的整体性特点使针对某一指标的改善可能会间接影响其他指标，并且投入力度不同，影响程度也有所差异。针对上述特性，将问题抽象成多选项二次联合背包模型，通过二次背包特性表示态势评估指标项之间的相互影响，通过多选项背包特性来表示单个指标项的多种投入可能。最后对其做半定规划松弛，采用分支定界法对问题进行求解。实验证明了算法的准确性和高效性。

关键词: 资源分配, 态势感知, 多选项二次联合背包, 半定松弛

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.

Key words: resource allocation, situation awareness, multiple-choice quadratic knapsack, semi-definite relaxation

孙岩炜,郭云川,张玲翠,方滨兴. 基于多选项二次联合背包的态势感知资源分配算法[J]. 通信学报, 2016, 37(12): 56-66.

Yan-wei SUN,Yun-chuan GUO,Ling-cui ZHANG,Bin-xing FANG. Resource allocation algorithm for situation awareness based on multiple-choice quadratic knapsack[J]. Journal on Communications, 2016, 37(12): 56-66.

图/表 11

图1

图2

图3

图4

表1

图5

表2

图6

图7

图8

图9

参考文献 39

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	TAMASSIA R , PALAZZI B , PAPAMANTHOU C . Graph drawing for security visualization[C]// International Symposium on Graph Drawing. Springer Berlin Heidelberg, 2008:2-13.
[7]	TADDA G P , SALERNO J S . Overview of cyber situation aware-ness[M]. Cyber Situational Awareness. Springer US, 2010:15-35.
[8]	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.
[9]	Federal Office for Information Security: 13 EL: Cross-reference tables of the IT-grundschutz catalogues: 13th version (2013)[EB/OL]. .
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	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.
[16]	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.
[17]	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.
[18]	FIELDER A , PANAOUSIS E , MALACARIA P , et al. Decision sup-port approaches for cyber security investment[J]. Decision Support Systems, 2016,86:13-23.
[19]	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.
[20]	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.
[21]	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.
[22]	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.
[23]	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.
[24]	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.
[25]	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.
[26]	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.
[27]	SAWIK T . Selection of optimal countermeasure portfolio in IT secu-rity planning[J]. Decision Support Systems, 2013,55(1):156-164.
[28]	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.
[29]	GORDON L A , LOEB M P . The economics of information security investment[M]// Economics of Information Security. Springer US, 2004:105-125.
[30]	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.
[31]	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.
[32]	BRETTHAUER K M , SHETTY B . Quadratic resource allocation with generalized upper bounds[J]. Operations Research Letters, 1997,20(2):51-57.
[33]	HAHN P , GRANT T . Lower bounds for the quadratic assignment problem based upon a dual formulation[J]. Operations Research, 1998,46(6):912-922.
[34]	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.
[35]	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.
[36]	CAPRARA A , PISINGER D , TOTH P . Exact solution of the quadratic knapsack problem[J]. Informs Journal on Computing, 1999,11(2):125-137.
[37]	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.
[38]	KELLERER H , PFERSCHY U , PISINGER D . Introduction to NP-completeness of knapsack problems[M]. Springer Berlin Heidel-berg, 2004.
[39]	BRETTHAUER K M , SHETTY B . The nonlinear knapsack prob-lem–algorithms and applications[J]. European Journal of Operational Research, 2002,138(3):459-472.

防护措施	针对威胁个数	负面影响个数
增加网络异构化	5	2
对网络冗余备份	6	1
加入诱导性欺骗	8	3
分散隔离管理网络	10	3
加入应急响应模块	11	1
集中管理信息资源	3	4

n	半定规划松弛度	CPLEX松弛度
10	12.5%	75.1%
15	28.3%	86.9%
20	22.5%	75.4%
25	16.7%	68.8%
30	13.4%	89.8%
35	36.8%	72.5%
40	19.3%	90.2%
45	28.6%	88.5%