Binary Archimedes Optimization Algorithm for Computing Dominant Metric Dimension Problem

In this paper,we consider the NP-hard problem of finding the minimum dominant resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B.A resolving set is dominating if every vertex of G that does not belong to B is a neighbor to some vertices in B.The dominant metric dimension of G is the cardinality number of the minimum dominant resolving set.The dominant metric dimension is computed by a binary version of the Archimedes optimization algorithm(BAOA).The objects of BAOA are binary encoded and used to represent which one of the vertices of the graph belongs to the dominant resolving set.The feasibility is enforced by repairing objects such that an additional vertex generated from vertices of G is added to B and this repairing process is iterated until B becomes the dominant resolving set.This is the first attempt to determine the dominant metric dimension problem heuristically.The proposed BAOA is compared to binary whale optimization(BWOA)and binary particle optimization(BPSO)algorithms.Computational results confirm the superiority of the BAOA for computing the dominant metric dimension.

基于深度学习的Linux系统DKOM攻击检测

直接内核对象操纵(DKOM)攻击通过直接访问和修改内核对象来隐藏内核对象,是主流操作系统长期存在的关键安全问题。对DKOM攻击进行基于行为的在线扫描适用的恶意程序类型有限且检测过程本身易受DKOM攻击影响。近年来,针对潜在受DKOM攻击的系统进行基于内存取证的静态分析成为一种有效和安全的检测方法。现有方法已能够针对Windows内核对象采用图神经网络模型进行内核对象识别,但不适用于Linux系统内核对象,且对于缺少指针字段的小内核对象的识别有效性有限。针对以上问题,设计并实现了一种基于深度学习的Linux系统DKOM攻击检测方案。首先提出了一种扩展内存图结构刻画内核对象的指针指向关系和常量字段特征,利用关系图卷积网络对扩展内存图的拓扑结构进行学习以实现内存图节点分类,使用基于投票的对象推测算法得出内核对象地址,并通过与现有分析框架Volatility的识别结果对比实现对Linux系统DKOM攻击的检测。提出的扩展内存图结构相比现有的内存图结构能更好地表示缺乏指针但具有常量字段的小内核数据结构的特征,实现更高的内核对象检测有效性。与现有基于行为的在线扫描工具chkrootkit相比,针对5种现实世界Rootkit的DKOM行为,所提方案实现了更高的检测有效性,精确度提高20.1%,召回率提高32.4%。

一阶逻辑中基于treelet图神经网络的前提选择

前提选择是解决自动定理证明器面对大规模问题时性能降低的有效方法。当前面向一阶逻辑中前提选择的主流图神经网络忽略了逻辑公式图内部的节点顺序信息。针对此问题,将一种面向高阶逻辑公式的保序方法拓展到一阶逻辑中,并提出了一种基于treelet的图神经网络模型。该模型在信息聚合时一部分聚合中心节点的父、子节点信息,另一部分聚合节点顺序信息。实验分析表明:基于treelet的图神经网络模型在前提选择任务中比最优的主流图神经网络模型的分类准确率提高了约2%。

Binary Tree Petersen网络性质及算法研究

基于Petersen图，提出了Binary Tree Petersen的网络结构，并对其特性进行了研究，证明了Binary Tree Petersen网络具有正则性以及良好的可扩展性，同时还具有比RP（k）、2-DToms更短的直径和良好的并行能力．另外，还基于Binary Tree Petersen网络分别给出了其上的单播和广播路由算法，证明了通信效率都为2j＋4．

基于数据依赖的跨架构二进制代码相似性分析

二进制代码相似性检测(Binary Code Similarity Detection,BCSD)技术在逆向工程、漏洞检测、恶意软件检测、软件抄袭以及补丁分析等学术应用领域发挥着重要作用。大多数研究已经集中在对二进制函数进行控制流嵌入和基于自然语言处理(Natural Language Processing,NLP)技术的底层代码嵌入技术的研究之中。然而,需要指出的是,函数在实际运行中不仅包含控制流信息,还包括数据流语义信息。因此,如何全面抽象函数的语义特征显得尤为关键。为此,该文提出了BS-DD模型,这是一个融合了控制流和数据依赖关系的二进制函数相似性判断框架。通过模拟执行二进制代码的方法来提取语义信息,并运用化简算法构建数据依赖关系图。最后,借助图神经网络进行相似性判别。对来自开源社区的7个广泛使用的软件进行了不同组合的编译,并在此基础上设计了3个不同的任务场景以及真实的漏洞检测实验,用以比较BS-DD方法与最新基于数据流的BCSD方法的性能。实验结果显示,该模型在召回率和MRR(Mean Reciprocal Rank)分数方面取得了显著的提高。在真实环境的漏洞检测中,该模型也始终优于其他方法。

Buffer Overflow Detection on Binary Code

Most solutions for detecting buffer overflow are based on source code. But the requirement tor source code is not always practical especially for business software. A new approach was presented to detect statically the potential buffer overflow vulnerabilities in the binary code of software. The binary code was translated into assembly code without the lose of the information of string operation functions. The feature code abstract graph was constructed to generate more accurate constraint statements, and analyze the assembly code using the method of integer range constraint. After getting the elementary report on suspicious code where buffer overflows possibly happen, the control flow sensitive analysis using program dependence graph was done to decrease the rate of false positive. A prototype was implemented which demonstrates the feasibility and efficiency of the new approach.

A Novel Symbolic Algorithm for Maximum Weighted Matching in Bipartite Graphs

The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.

A novel facial emotion recognition scheme based on graph mining

Recent years have seen an explosion in graph data from a variety of scientific,social and technological fields.From these fields,emotion recognition is an interesting research area because it finds many applications in real life such as in effective social robotics to increase the interactivity of the robot with human,driver safety during driving,pain monitoring during surgery etc.A novel facial emotion recognition based on graph mining has been proposed in this paper to make a paradigm shift in the way of representing the face region,where the face region is represented as a graph of nodes and edges and the gSpan frequent sub-graphs mining algorithm is used to find the frequent sub-structures in the graph database of each emotion.To reduce the number of generated sub-graphs,overlap ratio metric is utilized for this purpose.After encoding the final selected sub-graphs,binary classification is then applied to classify the emotion of the queried input facial image using six levels of classification.Binary cat swarm intelligence is applied within each level of classification to select proper sub-graphs that give the highest accuracy in that level.Different experiments have been conducted using Surrey Audio-Visual Expressed Emotion(SAVEE)database and the final system accuracy was 90.00%.The results show significant accuracy improvements(about 2%)by the proposed system in comparison to current published works in SAVEE database.

The Symbolic OBDD Algorithm for Finding Optimal Semi-matching in Bipartite Graphs

The optimal semi-matching problem is one relaxing form of the maximum cardinality matching problems in bipartite graphs, and finds its applications in load balancing. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate Boolean functions efficiently. OBDD-based symbolic algorithms appear to give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic OBDD formulation and algorithm for the optimal semi-matching problem in bipartite graphs. The symbolic algorithm is initialized by heuristic searching initial matching and then iterates through generating residual network, building layered network, backward traversing node-disjoint augmenting paths, and updating semi-matching. It does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Our simulations show that symbolic algorithm has better performance, especially on dense and large graphs.

Wiener Number of Some Subgraphs in Archimedean Tilings

In this paper, we deduce Wiener number of some connected subgraphs in tilings (4, 4, 4, 4) and (4, 6, 12), which are in Archimedean tilings. And compute their average distance.

CONVERGENCE ANALYSIS AND MRALLEL IMPLEMENTION FOR THE DIRECTEDGRAPH -ALGORITHM

In this paper we discuss the convergence of the directed graph-algorithm for solving a kind of optimization problems where the objective and subjective functions are all separable, and the parallel implementation process for the directed graph -algorithm is introduced.

基于元动作的机电产品FTA分析方法

为解决传统故障树(fault tree analysis, FTA)分析中建树困难、过于庞大和定性分析复杂的问题,提出了一种基于元动作全故障模式与改进二元决策图的故障树分析方法。首先,根据元动作全故障模式分析方法找出关键故障模式;其次,针对关键故障模式,按照故障模式-参数-结构-原因的原则来查找基本原因,从而得到关键故障模式的故障树;再次,采用改进的二元决策图(binary decision graph, BDG)对建立的故障树进行定性分析,得到最小割集,并通过定量计算得到各底事件的相对概率重要度,找到关键的故障原因,为机电产品的设计和改进提供参考依据;最后,以三级行星齿轮减速器为例进行基于元动作的故障树分析,并与传统的故障树分析方法进行比较。最终结果验证了所述方法的适用性和有效性,提高了机电产品故障分析的通用性和分析效率。

基于机载LiDAR点云的建筑物多细节层次建模方法

机载激光雷达点云(LiDAR)重建大范围建筑物模型一直是实景三维建模的热点问题,由于机载激光点云稀疏、建筑物立面数据缺失,给模型自动化重建带来了极大的挑战。为了解决该问题,本论文研究基于图优化理论重建建筑物多细节层次(LOD)模型。首先,对原始点云进行自动化滤波,分离地面点和非地面点,对地面点构建数字高程模型(DEM),对非地面点半自动提取单体化建筑物点云。然后,基于滚球法(Alpha shape)提取建筑物边界,利用通用图优化方法(G2O)对误差线进行全局一致性改正,获得规则化的二维边框。并基于建筑物屋顶三维高程及DEM高程值重建建筑物LOD1模型。其次,根据点云的高程差异生成高程栅格图,从高程栅格图提取建筑物轮廓线,对轮廓线进行简化、规则化、聚类,并将规则后的边界线拉伸获取建筑物立面结构,弥补建筑物立面数据缺失对建模的影响。最后,将屋顶平面相交、建筑物立面裁剪,对候选平面进行二元图割全局优化,选择最能表达建筑物结构的平面,以此重建建筑物LOD2模型。本论文选择北京市2017年机载激光点云进行实验,结果表明,本文提出的方法可以稳健地重建建筑物多细节层次模型,LOD2模型距离偏差为0.22 m,LOD1模型距离偏差为0.71 m,整体模型精确度高;针对1147个建筑物,LOD2和LOD1模型重建时间分别为1290s和1097s,具有较高的自动化程度和建模效率。

基于二元决策图的水电厂事故风险控制系统

为了控制水电厂事故风险,保证水电厂的安全生产,设计基于二元决策图的水电厂事故风险控制系统。采集人员和作业现场的相关数据和信息,对数据安全控制、缓存以及过滤后,应用层依据存储的信息数据,通过生成二元决策图评估数据的事故发生比率以及风险重要程度,将事故风险信息存储至事故风险库,将结果呈现至驱动层,完成事故风险可视化以及远程外联,实现水电厂事故风险控制。实例测试结果表明,该系统可有效完成事故风险评估,准确获取电子标签信息的采集和识别,在合理的网络节点部署范围可全部接收信息传输字节,多任务执行的最大抖动范围在5~-4 ms,符合默认抖动范围,事故风险控制效果良好。

基于图论的配电网故障行波定位新算法

配电网结构复杂,分支多,故障点定位困难。传统基于输电线路单端或双端信息的故障定位算法难以满足配电网高精度故障定位要求。提出了基于多端时间信息的配电网故障行波定位新算法,构建了配电网关联矩阵和距离矩阵,给出了故障分支的判别方法;基于二叉树模型,根据配电网末端的行波到达精确时间信息和配电网拓扑结构矩阵,剔除无效行波波头时间,综合利用有效的行波波头时间信息,实现配电网故障的实时精确定位。EMTP仿真结果表明,该方法能实现配电网故障的准确定位。

二进制翻译中解析多目标分支语句的图匹配方法

二进制翻译技术现已成为实现软件移植的重要手段．在二进制翻译系统中，如何有效地挖掘程序的代码并对其进行高效翻译是影响系统性能的关键，而二进制代码中间接跳转语句的存在，使得静态时难以得到它的跳转目标，影响了代码的发掘率和最终的翻译效果．在通常的应用程序中，间接跳转指令经常用来实现多目标分支语义，分支目标存放在跳转表中．提出了一种解析多目标分支语句及其跳转表的方法，能够挖掘出间接跳转的目标，进而对其进行有效翻译并提高二进制翻译系统的性能．该方法提出使用语义图来对预期语义进行刻画和表达．语义图能够对考察的指令序列进行语义提取，识别出与预期语义相匹配的指令流，还可以应对编译器在不同优化选项下生成的指令，并能有效滤除不相关指令带来的干扰．实验结果表明，对于SPEC CINT2000中的部分测试用例，代码翻译的覆盖率可以提高9．85％～22．13％，相应带来的性能提升可达到8．30％～17．71％，而使用的算法时间复杂度仅为O（1）．

基于二叉树的上下文相关L-系统实现

从底层数据结构的角度讨论了上下文相关L-系统实现中的几个关键问题.结合L-系统的语法,解释了以二叉树为底层数据结构的新系统设计机理,提出了生长方式树和生长状态树的概念,给出了新的数据结构形式下生长状态演化算法的实现.与采用线性数组实现的L系统相比,新系统很好地模拟了L-系统本身的树形逻辑结构,简化了L-系统中上下文搜索的过程,在生长模拟环节有更高的时空效率,且具备更好的可扩展性.以虚拟植物生长为背景,介绍了如何基于新数据结构进行虚拟植物绘制和绘制优化,并通过实例验证了新算法的有效性.

基于图划分的大电网拓扑分析

为支撑大电网在线实时监控和分析,提出了一种基于图划分的大电网拓扑分析方法。该方法首先根据智能电网调度控制系统电网建模特点,给出了基于图论的电网层次结构、拓扑结构、厂站母线分析和系统网络分析模型。然后基于图划分建立了并行网络拓扑和局部拓扑修正的数学模型,并根据该模型设计了大电网并行网络拓扑的实现方法。最后基于共享内存编程模型在智能电网调度控制系统中研发了快速网络拓扑分析服务功能。所提出的模型和方法实现了大电网并行网络拓扑分析的无锁计算,避免了多线程数据竞争导致的阻塞耗时问题。对实际系统进行仿真测试,结果表明了该方法的准确性、实时性和有效性。

改进二进制粒子群优化算法在配电网络重构中的应用

配电网络重构是一个非常复杂的大规模组合优化问题。网络重构中,能否得到有效解,即保证辐射状网络,是一个很关键的问题。对电网拓扑进行简化,配合破圈法更新粒子,得到100%的有效解,大大提高了计算速度。提出一种应用于配电网络重构的改进二进制粒子群优化算法,并结合禁忌搜索算法,使PSO算法跳出局部最优化陷阱,改善了算法的搜索效果,加快了寻优速度。最后对IEEE 69节点系统进行计算,并与相关文献结果进行对比,表明本文改进算法具有快速、高效的全局寻优能力。

结合光谱、纹理与形状结构信息的遥感影像分割方法

针对目前遥感影像分割中多特征利用的问题,提出一种综合利用光谱、纹理与形状信息的分割方法。该方法在进行初始分割的基础上,统计区域的光谱和LBP纹理特征;然后依据光谱、纹理与形状特征计算相邻区域之间的异质性,并以此为基础构建区域邻接图(region adjacency graph,RAG);最后在邻接图的基础上采用逐步迭代优化算法进行区域合并获取最终分割结果。采用QuickBird和SAR影像的分割试验,证明该算法能充分利用影像中地物的光谱、纹理与形状信息,分割效果良好,效率高。