基于程序依赖图的克隆检测及改进

为了发现克隆代码并检测出其中的错误,研究了多种克隆代码检测技术,对于其中一种检测——基于程序依赖图(PDG)的克隆检测进行了详细介绍,并举例对该过程进行了分析.这样检测虽然相比其它检测技术对于断层克隆有着独特的优势,但是对于功能克隆却起不到理想效果.为了使克隆检测更加详尽及精确,以及能有效地检测功能克隆,对程序依赖图的形成过程进一步改进,在语法上对于语句进行断层,并对其进行相应规范.     

使用类型限定的系统依赖图检测整型错误

目前大多数的源码安全审计工具在整型错误的检测上具有局限性,往往只能检测整型溢出类型的漏洞。针对这个问题,对已有的系统依赖图（system dependence graph,SDG）检测模型进行了改进,结合类型限定理论提出了基于类型限定的系统依赖图（type-qualified SDG, QSDG）检测模型。该模型不仅可以用来检测C代码中潜在的绝大多数整型错误,而且还能根据其出错原因将其分类到所定义的八种错误类型。与SDG检测模型仅采用图同构算法进行检测相比,先使用类型推断算法再对QSDG进行检测可以降低检测所花费的时间。     

基于状态转换图的入侵检测模型STGIDM

Pattern Match based on the serial of system calls is one of the widely used intrusion detection technologies, while the courses that cause intrusion frequently accord with chosen pattens when programs monitored are complex and the number of chosen patterns is large, which always causes some intrusions to be neglected. In this a rticle, anew Intrusion Detection Model based on State Transition Graph is put forward. In this model, the programs‘ properties are accurately reflected by State Transition Graph, and transitions are introduced between states that aren‘t conjoint. Moreover, the number of transitions between states that aren‘t conjoint is one of key factors to deduce intrusions during matching.     

基于与或依赖图的多Agent系统任务分解算法

针对多Agent系统任务分解问题,提出了基于与或依赖图的任务分解模型及算法.通过引入与或依赖图概念,以描述任务中各操作之间的依赖关系,然后给出了构造操作集的与或依赖图算法,最后在此基础上设计了任务的分解模型及其算法.算法优点是能区分出各操作之间是否具有并行性且能分解出所有可并行执行的操作集,而且由于按与或依赖图中的各层而不是按各操作进行循环,其循环的次数大大减少.实例应用表明,该算法具有较高的时间与空间效率,并支持任务的动态分解.     

基于简化系统依赖图的静态粗粒度切片方法

基于系统依赖图是计算面向对象程序切片的一个有效方法.但是,系统依赖图的缺点是太复杂,而且在建立系统依赖图的过程中容易出错,一旦出现错误就可能导致切片结果的不准确.通过对系统依赖图进行简化,得到了简化的系统依赖图.它省略了那些表示输入参数和输出参数的结点和概括边.同时,还定义了一种面向对象程序的粗粒度切片概念,讨论了它的性质,分析了它与细粒度切片的关系,并基于简化的系统依赖图计算面向对象程序的粗粒度切片.最后还讨论了切片技术的简单实现.     

基于依赖图的信息流图构建方法*

信息流分析法是一种有效的隐通道搜索方法,用信息流图来描述系统中信息流的流动情况。直接基于系统源代码生成系统信息流图,由于信息流的传递关系,会引进大量系统中不存在的信息流路径。利用程序依赖图先处理系统信息流中的传递关系,然后再进行信息流图的生成,从而减少引入系统中不存在的信息流路径,减少信息流分析时的工作量。     

构造面向对象系统依赖图技术研究

本文分析了现有面向对象图形表示方案存在的问题,在此基础之上,提出了基于波动效应分析构造面向对象系统依赖图的方法,通过引入波动效应分析,来完善面向对象程序的语义和减小构图的复杂性,在波动效应分析的基础之上,构造类图、改造面向过程的系统依赖图,结合两个图来描述面向对象程序。通过类图描述不同类之间的关联关系和类的内部定义,在类图中表达过程依赖,改造面向过程的系统依赖图用于表达控制依赖和数据依赖。文中给出了计算波动效应和构造系统依赖图的算法描述。     

基于级别转换的入侵检测系统的研究与实现

根据事件分级的思想，结合历史事件序列的相关性对入侵进行分析,给现有的入侵事件划分了安全级别，并在此基础上提出了级别转换算法，解决了以前的入侵检测系统中只对单个事件进行分析的缺点,使入侵检测系统具有预警功能,并可以对黑客攻击的将来步骤进行预测。该文还对基于该思想实现的入侵检测系统的数据处理流程、软件体系结构、脚本语法规则进行了介绍。     

基于级别转换的侵入检测系统的研究与实现

根据事件分级的思想，结合历史事件序列的相关性对入侵进行分析，给现有的入侵事件划分了安全级别，并在此基础上提出了级别转换算法，解决了以前的入侵检测系统中只对单个事件进行分析的缺点，使入侵检测系统具有预警功能，并可以对黑客攻击的将来步骤进行预测，该文还对基于该思想实现的入侵检测系统的数据处理流程，软件体系结构、脚本语法规则进行了介绍。     

Slithice:一个基于系统依赖图的Java程序切片工具

当前程序切片的相关理论已经较为成熟,但针对Java程序的静态切片工具却非常少见。为便于展开切片应用研究,设计并实现了一个基于系统依赖图的Eclipse切片插件——Slithice。该插件支持不同粒度的底层分析和系统依赖图构建,从而可以使切片算法能够在精度和性能之间进行权衡,适应各种规模程序的分析需要。     

基于依赖关系图和通用漏洞评分系统的网络安全度量

管理人员通常使用一些网络安全指标作为度量网络安全的重要依据。通用漏洞评分系统（CVSS）是目前人们普遍认同的网络度量方式之一。针对现有的基于CVSS的网络安全度量无法精确测量网络受到攻击的概率和影响两方面得分的问题，提出一种基于依赖关系图和CVSS的改进基础度量算法。首先发掘攻击图中漏洞节点的依赖关系，构建依赖关系图；然后根据依赖关系修改CVSS中漏洞的基础度量算法；最后聚合整个攻击图中的漏洞得分，得到网络受到攻击的概率及影响两方面的得分。采用模拟攻击者进行仿真实验，结果表明，该算法在算法精确度和可信度方面明显优于汇总CVSS分数算法，更加接近实际仿真结果。     

基于效用图的依赖关系与协商策略研究

依赖关系一直是多议题协商的重点和难点.在基于依赖关系的多议题协商背景下,对依赖关系和依赖度进行了严格的定义和度量.在协商过程中,协商Agent强化了自身的协商策略,并使用多目标遗传协商算法对协商进行优化.实验结果表明,在该协商背景下依赖关系的定义以及依赖强度的度量是合理的,卖方Agent使用多目标遗传协商算法和各种协商策略是可行的,并取得了较好的协商效果,且使协商结果迭到了pareto最优.     

基于约束依赖图的并发程序模型检测工具

模型检测是一种基于状态空间搜索的自动化验证方法,可以有效地提升程序的质量.然而,由于并发程序中线程调度的不确定性以及数据同步的复杂性,对该类程序验证时存在更为严重的状态空间爆炸问题.目前,大多采用基于独立性分析的偏序约简技术缩小并发程序探索空间.针对粗糙的独立性分析会显著增加需探索的等价类路径问题,开发了一款可细化线程迁移依赖性分析的并发程序模型检测工具CDG4CPV.首先,构造了待验证可达性性质对应的规约自动机;随后,根据线程迁移边的类型和共享变量访问信息构建约束依赖图;最后,利用约束依赖图剪裁控制流图在展开过程中的独立可执行分支.在SV-COMP 2022竞赛的并发程序数据集上进行了对比实验,并对工具的效率进行比较分析.实验结果表明,该工具可以有效地提升并发程序模型检测的效率.特别是,与基于BDD的程序分析算法相比,该工具可使探索状态数目平均减少91.38%,使时间和空间开销分别平均降低86.25%和69.80%.     

基于依赖图的硬件事务存储技术研究

事务存储技术能够简化并行程序中对共享资源的访问控制,是当前的研究热点之一.目前,多数基于硬件的事务存储系统采用基于冲突检测与处理的并发控制协议,当检测到两事务发生冲突时就中止二者之一.但是对事务间"冲突"更深入的分析表明,某些"冲突"并不一定会导致事务的回退,这种冲突称为"弱冲突".基于依赖图的硬件事务存储技术能够避免弱冲突引发的多余事务回退.模拟实验表明,基于依赖图的事务存储系统与基于冲突处理的事务存储系统相比具有明显的性能优势.     

基于依赖图的网络故障识别技术研究

给出了依赖图的概念性描述和形式化定义,在此基础上介绍了一个基于依赖图进行故障定位的算法,并对该算法进行了性能评价。     

基于图常量条件函数依赖的图修复规则发现

数据一致性是数据质量管理的一个重要内容。为了提升图数据一致性,大量关系型数据库中的数据依赖理论被引入到图数据库,包括图函数依赖、图关联规则等。图修复规则是最新提出的一种针对图数据的数据依赖规则,具有强大的修复能力,但目前尚无有效的挖掘算法。为了自动生成图修复规则并提高图数据修复的可靠性,提出一种将图常量条件函数依赖转化为图修复规则的方法(GenGRR)。通过图模式在图中匹配同构子图并映射成节点-属性二维表,从表中相应属性域中抽取错误模式把图常量条件函数依赖转化成图属性值修复规则;删去图模式中常量条件函数依赖RHS对应的节点与相连边生成图属性补充规则。基于最大公共同构子图筛选并验证生成图修复规则的一致性。在多个真实数据集上进行测试,验证相比图常量条件函数直接修复图数据,通过转化生成的图修复规则具有更好的修复效果。     

基于最佳并行度的任务依赖图调度

基于最佳并行度的任务依赖图调度策略充分利用编译时刻所得到的全局信息,采用横向和纵向任务合并,处理节点预分配,静态调度和动态调度相结合、集中式调度和分层调度相结合等措施,是一种简单的、具有较高效率的实用化调度方案.该调度方案能够在尽量压缩调度长度的情况下节约系统资源.     

基于能力依赖图的SEAndroid安全策略分析

SEAndroid作为Android系统安全机制的重要组成部分,直接关系到系统的安全性.在本文中,我们提出一种基于能力依赖图的SEAndroid安全策略分析方法.能力依赖图描述了实际Android系统中用户的能力迁移以及其SEAndroid子系统的访问控制配置.我们首先对SEAndroid的具体实现进行分析,收集安全策略和系统信息,并进行逻辑建模.然后,我们依据SEAndroid的策略判定模式设计逻辑推导规则,并以此利用逻辑编程的方式生成能力依赖图.基于能力依赖图,我们提取出可能的攻击路径和攻击模式.我们对多个AOSP发布的不同Android版本的SEAndroid访问控制系统子进行了评估与分析.我们发现随着Android版本的提升,其SEAndroid安全策略也进行了更新,新的SEAndroid对系统提供了更强的约束和保护.此外,我们在实验中发现了一种被黑客在实际攻击中使用到的攻击模式,从而验证我们方法的有效性.     

时间窗-时间依赖中国邮路问题的图转换算法

研究时间依赖网络上带时间窗的中国邮路问题（TDCPPTW）,该问题是对中国邮路问题的扩展,它考虑了时间因素,在实时软件测试等当前许多具有时间依赖性质的热门问题中更具优势。首先提出了一个新的图转换算法;然后,从理论上证明了该转换算法能够在伪多项式时间内将TDCPPTW转换为相应的广义乡村邮路问题（GRPP）;最后,建立了一个0/1线性整数规划模型用于求解转换后的问题,并对随机生成的12个实例进行了求解实验。