Network Defense Decision-Making Based on Deep Reinforcement Learning and Dynamic Game Theory

Existing researches on cyber attackdefense analysis have typically adopted stochastic game theory to model the problem for solutions,but the assumption of complete rationality is used in modeling,ignoring the information opacity in practical attack and defense scenarios,and the model and method lack accuracy.To such problem,we investigate network defense policy methods under finite rationality constraints and propose network defense policy selection algorithm based on deep reinforcement learning.Based on graph theoretical methods,we transform the decision-making problem into a path optimization problem,and use a compression method based on service node to map the network state.On this basis,we improve the A3C algorithm and design the DefenseA3C defense policy selection algorithm with online learning capability.The experimental results show that the model and method proposed in this paper can stably converge to a better network state after training,which is faster and more stable than the original A3C algorithm.Compared with the existing typical approaches,Defense-A3C is verified its advancement.

A novel method to reconstruct phylogeny tree based on thechaos game representation

We developed a new approach for the reconstruction of phylogeny trees based on the chaos game representation (CGR) of biological sequences. The chaos game representation (CGR) method generates a picture from a biological sequence, which displays both local and global patterns. The quantitative index of the biological sequence is extracted from the picture. The Kullback-Leibler discrimination information is used as a diversity indicator to measure the dissimilarity of each pair of biological sequences. The new method is inspected by two data sets: the Eutherian orders using concatenated H-stranded amino acid sequences and the genome sequence of the SARS and coronavirus. The phylogeny trees constructed by the new method are consistent with the commonly accepted ones. These results are very promising and suggest more efforts for further developments.

An efficient distributed algorithm for game tree search

This paper presents a distributed game tree search algorithm called DDS. Based on communication overhead, st,orage requirement, speed up, and oiller factors, the performance of algorithm DDS* is analysed, and the number of nodes searched with SSS as well as a-b algorithm. The simulation test shows that. DDS* is an efficient and practical search algorithm.

Performance Characterization of Parallel Game-tree Search Application Crafty

Game-tree search plays an important role in the field of Artificial Intelligence （AI）. In this paper, we characterize one parallel game-tree search workload in chess： the latest version of Crafty, a state of art program, on two Intel Xeon shared-memory multiprocessor systems. Our analysis shows that Crafty is latency-sensitive and the hash-table and dynamic tree splitting used in Crafty cause large scalability penalties. They consume 35%-50% of the running time on the 4-way system. Furthermore, Crafty is not bandwidth-limited.

基于攻击树的ICPS混合博弈风险评估

工业信息物理系统在国家基础设施领域极为重要,若被破坏将造成极大的影响.本文采用带博弈策略的攻击树模型进行风险评估.首先,根据系统中各个物理组件的“与”“或”关系和它们所具有的漏洞节点,建立ICPS的整体攻击树模型;然后,在攻击树的叶子节点中加入攻防混合博弈策略,给出攻击和防御方式的收益函数,以此求得不同防御方式发生的可能性概率;最后,以防御方式收益函数和发生的可能性概率求得每种防御方式的风险值,采用层次分析法和熵权法的综合赋权得出叶子节点风险值,以此求出根节点风险值进行评估.通过MATLAB仿真,求出攻击树根节点风险值确定废水发电厂模型的风险评估等级以及哪个物理层较为薄弱,若等级较高,可采取后续的评估寻找系统薄弱组件.

在游戏中利用邻域特性扩展的kd-tree及其查找算法

处理场景中数量庞大的各种对象间的交互是游戏的一类主要计算工作。将kd-tree用于组织场景,提高了这类计算的效率。传统算法采用树的层次遍历方式进行查找,处理跨节点情况时性能下降明显。提出了邻域特性概念以扩展传统kd-tree结构,增添了树节点间的平面邻接关系,且考虑了游戏对kd-tree的一些限定,设计了从起始节点向四周扩展的查找算法。经分析与实验证明,新算法比传统算法有约40%的性能提升且更稳定。

Irrational-Behavior-Proof Conditions for Stochastic Games over Event Trees

In this paper,the irrational-behavior-proof conditions in a class of stochastic dynamic games over event trees are presented.Four kinds of irrational-behavior-proof conditions are proposed by the imputation distribution procedure,and their relationships are discussed.More specific properties for the general transformation of characteristic functions are developed,based on which,the irrational-behavior-proof conditions are proved to be true in a transformed cooperative game.

基于合作博弈论的电梯修建成本分摊博弈

老旧小区加装电梯是目前城镇化建设中的一个重要议题.问题的关键之一是如何在需求和收益高度异质的业主间分摊电梯安装成本.该文以合作博弈论为基础构建了电梯博弈模型,证明了电梯博弈为凸博弈,并给出了两类基于最小支撑树博弈的推广Bird配置,其中第二类推广Bird配置与现行的成本分摊机制很相似,且满足成本单调性、人口单调性以及感知公平性.

回合制轨道博弈中MCTS算法的改进与应用

航天器回合制追逃博弈中的变轨感知延迟使得微分对策法求解困难,基于深度强化学习的博弈算法可解释性弱,在工程上的运用仍存在风险。针对航天器回合制追逃博弈问题,提出了一种预测价值积累的蒙特卡洛树搜索(PVA-MCTS)算法。该算法基于航天器轨道运动的可预知性,对博弈过程中的决策价值进行预测并积累,解决了航天器回合制追逃博弈奖励稀疏、时间跨度大的问题,采用的自适应扩展方法提升了学习效率。将其用于求解航天器回合制追逃博弈问题,并与蒙特卡洛树搜索(MCTS)算法求解得到的结果对比,结果表明PVA-MCTS算法对追踪航天器和逃逸航天器分别有约27.6%的追捕用时缩短和约6.8%的逃逸时间延长。该算法的提出可加快推进后续轨道博弈技术在非合作目标接近、碰撞规避等领域应用的落实落地。

基于行为树的多星轨道追逃博弈方法

多智能体强化学习是解决空间追逃博弈问题的一类有效方法,但在多星追逃博弈场景下存在复杂性高、训练时间长、难以收敛等问题。本文提出一种基于行为树的多星轨道追逃博弈方法,将对多个目标的复杂追逃博弈问题分解为对单一目标的追逃博弈问题。利用行为树构建多星追逃任务分配与博弈决策框架,以最大化追击成功概率为目标建立最优任务分配模型,并利用遗传算法进行求解,实现多星追逃任务快速分解;对于分配的追击任务,各卫星自主选择多智能体深度确定性策略梯度算法训练得到的博弈策略开展博弈决策。结果表明,本文所提方法能将多星轨道博弈任务有效分解,并在行为树的驱动下成功完成对目标的追击。

Fuzzy mathematics and game theory based D2D multicast network construction

Device to device(D2 D) multi-hop communication in multicast networks solves the contradiction between high speed requirements and limited bandwidth in regional data sharing communication services. However, most networking models demand a large control overhead in eNodeB. Moreover, the topology should be calculated again due to the mobility of terminals, which causes the long delay. In this work, we model multicast network construction in D2 D communication through a fuzzy mathematics and game theory based algorithm. In resource allocation, we assume that user equipment(UE) can detect the available frequency and the fuzzy mathematics is introduced to describe an uncertain relationship between the resource and UE distributedly, which diminishes the time delay. For forming structure, a distributed myopic best response dynamics formation algorithm derived from a novel concept from the coalitional game theory is proposed, in which every UE can self-organize into stable structure without the control from eNodeB to improve its utilities in terms of rate and bit error rate(BER) while accounting for a link maintenance cost, and adapt this topology to environmental changes such as mobility while converging to a Nash equilibrium fast. Simulation results show that the proposed architecture converges to a tree network quickly and presents significant gains in terms of average rate utility reaching up to 50% compared to the star topology where all of the UE is directly connected to eNodeB.

Prediction Distortion in Monte Carlo Tree Search and an Improved Algorithm

Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one of the key AI techniques developed recently that enabled AlphaGo to defeat a legendary professional Go player. What makes MCTS particularly attractive is that it only understands the basic rules of the game and does not rely on expert-level knowledge. Researchers thus expect that MCTS can be applied to other complex AI problems where domain-specific expert-level knowledge is not yet available. So far there are very few analytic studies in the literature. In this paper, our goal is to develop analytic studies of MCTS to build a more fundamental understanding of the algorithms and their applicability in complex AI problems. We start with a simple version of MCTS, called random playout search (RPS), to play Tic-Tac-Toe, and find that RPS may fail to discover the correct moves even in a very simple game position of Tic-Tac-Toe. Both the probability analysis and simulation have confirmed our discovery. We continue our studies with the full version of MCTS to play Gomoku and find that while MCTS has shown great success in playing more sophisticated games like Go, it is not effective to address the problem of sudden death/win. The main reason that MCTS often fails to detect sudden death/win lies in the random playout search nature of MCTS, which leads to prediction distortion. Therefore, although MCTS in theory converges to the optimal minimax search, with real world computational resource constraints, MCTS has to rely on RPS as an important step in its search process, therefore suffering from the same fundamental prediction distortion problem as RPS does. By examining the detailed statistics of the scores in MCTS, we investigate a variety of scenarios where MCTS fails to detect sudden death/win. Finally, we propose an improved MCTS algorithm by incorporating minimax search to overcome prediction distortion. Our simulation has confirmed the effectiveness of the proposed algorithm. We provide an estimate of the additional computational costs of this new algorithm to detect sudden death/win and discuss heuristic strategies to further reduce the search complexity.

基于GBDT算法的游戏销量预测模型研究

随着网络游戏的快速兴起,精确的游戏销量预测具有较高的商业价值,能够明确各方投资方向,提高收益,形成合作共赢。本文以影响游戏销量的特征数据为样本,建立基于梯度提升决策树(Gradient Boosting Decision Tree,GBDT)算法的游戏销量预测模型;并将GBDT模型预测结果与决策树、线性回归、极端随机树进行对比分析。分析表明,本文所建立的游戏销量预测模型较其它预测模型具有较高的拟合优度,预测效果更好,且在预测阶段的计算速度快,在分布稠密的数据集上,泛化能力和表达能力较好。

事件故障状态量子博弈过程的参与者收益研究

为了解事件故障状态量子博弈过程中参与者收益随各影响因素的变化情况,提出在空间故障树(Space Fault Tree, SFT)框架内,以事件故障状态为对象,对参与者收益进行研究。事件故障状态使用量子态表示,管理者和操作者的不同行为对事件故障状态的作用使用博弈表示。考虑因素包括安全产出价值、安全收益分配系数、安全措施成本。研究了事件故障状态与量子博弈的关系;纠缠与非纠缠态下的参与者收益;参与者收益受到各因素影响的特征等。研究得到了管理者和操作者考虑纠缠和非纠缠态的收益函数。结合SFT理论方法,提出了针对收益的因素重要度、因素联合重要度、收益风险区和安全区、因素区域重要度。理论上SFT可用于量子博弈参与者收益的分析。也论述了使用因素空间理论解决该问题的可能性。

基于博弈动态影响图的股市趋势推理算法

股票市场是一个复杂非线性动态系统,具有高度不确定性和多变性,股市趋势预测是数据挖掘领域的一个研究热点。针对基于数据驱动方法所生成的模型鲁棒性差,训练良好的模型不适应实际需要的问题,提出了一种多Agent博弈动态影响图模型(Mulit-Agent Game Dynamic Influence Diagrams,MAGDIDs)。首先,从博弈的角度引入多方和空方作为股市的行为主体(Agent),提取行为主体的相关特征;然后,利用能量表示博弈主体的力量大小,并对行为主体特征进行量化融合;进而引入博弈策略,构建多Agent博弈动态影响图模型,对于股市行为主体的博弈过程进行建模;最后,利用联合树的自动推理技术,预测股市趋势。在实际数据上进行实验,实验结果表明多空博弈趋势预测算法具有良好性能。

基于Qt和博弈算法的五子棋游戏设计

研究了五子棋博弈算法的关键技术,设计并实现五子棋游戏对战平台。以Qt多线程机制和TCP/IP协议为基础,设计P2P和C/S网络混合模型,并以Socket网络编程技术实现五子棋游戏的局域网对战。采用极大极小值搜索算法实现机器人博弈,并通过α-β剪枝算法和AC匹配算法优化博弈算法。结果表明,该设计可以实现同局域网下网络对弈功能,并且AI的计算时间得到较大的缩减。

基于非合作动态博弈的网络安全主动防御技术研究

目前基于博弈的网络安全主动防御技术大多采用静态博弈方式.针对这种静态方式无法应对攻击者攻击意图和攻击策略动态变化的不足,基于非合作、非零和动态博弈理论提出了完全信息动态博弈主动防御模型.通过"虚拟节点"将网络攻防图转化为攻防博弈树,并给出了分别适应于完全信息和非完全信息两种场景的攻防博弈算法.理论分析和实验表明相关算法在复杂度不高于同类算法的前提下:1)不仅适应于完全信息博弈场景,而且在非完全信息的特殊场景下仍能够得到合理的解;2)与采用静态博弈给出的以概率形式描述的混合策略Nash均衡解相比,给出的从子博弈精炼Nash均衡中抽出的解具有更好的可理解性和可操作性.

安全协议的博弈论机制

在博弈论框架下,基于纳什均衡设计安全协议的计算和通信规则.首先,提出安全协议的扩展式博弈模型,结合通用可组合安全的思想给出安全通信协议博弈参与者集合、信息集、可行策略、行动序列、参与者函数、效用函数等定义;在该模型下的安全协议能安全并发执行.其次,根据博弈的纳什均衡给出安全通信协议的形式化定义.最后,基于该机制给出一个安全协议实例,并分析该安全协议博弈机制的有效性.

中国象棋计算机博弈系统评估函数的自适应遗传算法实现

使用自适应遗传算法解决中国象棋计算机博弈问题.将博弈问题分解为搜索引擎、走法生成、评估函数和开局库四大模块,然后将自适应遗传算法引入到评估函数中,通过锦标赛算法对评估函数中的参数组合进行自动调整和优化.设计并开发了基于上述方法的离线自学习系统,实验结果证明提高了程序的棋力.

基于博弈论的网络社区舆情传播模型

针对网络社区动态、交互的舆情传播问题,提出了基于博弈论的舆情传播模型(POBGT)。利用在动态概率条件下的博弈策略构成博弈树和收益矩阵,从网络社区内部与外部分别对动态舆情传播进行分析;构建的模型能够从动态和交互两方面描述传播过程,最终能够形成稳定的状态。仿真结果表明,网络社区中舆情传播在一般情况下具有初期传播平稳,后期倾向某一方形成具有一定影响的舆论。