摘要:提出了一种链表抽象表示方法.该方法隐式存储链表结点之间的边信息,并采用了一种紧致的链表状态表示,存储开销较低,且维护了链表长度信息,精确度较高.具体而言,根据变量对链表结点的可达性质定义了变量可达向量,采用带计数的变量可达向量集描述链表的形态及数量性质,并定义了基本链表操作的抽象语义.通过简单扩展,该方法可以建模包括环形链表在内的所有单向链表.最后,为了验证该链表抽象方法的正确性,在符号执行框架中进行实验,并对常见链表操作程序的运行时错误、长度相关性质等关键性质进行了分析与验证.

摘要:推测多线程(speculative multithreading,简称SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,基于控制流图和分支预测技术的线程划分方法,不可避免地会受到划分路径上所存在的控制依赖和数据依赖的制约.目前,在传统的线程划分算法中存在的一个重要问题是,在对划分路径进行选取时只考虑了控制依赖影响却不能有效地综合考虑数据依赖的影响,进而导致不能选取最佳的划分路径.因此,针对传统方法中这种依赖评估方法效率低下的问题,设计并实现了一种基于路径优化的线程划分算法.该算法通过引入基于程序切片技术的预计算方法,建立一种路径评估方法来评估程序间的控制和数据依赖.同时,引入控制线程体大小的启发式规则,以便有效地解决负载不平衡的问题.基于Olden 测试集的测试结果表明,所提出的算法可以有效地对非规则程序进行划分,其平均加速比可以达到1.83.

摘要:选取了10 种具有代表性的代码坏味进行研究.从每种代码坏味的产生原因、症状、对软件的影响以及相应的处理这4 个方面进行分析,提出了一个代码坏味处理顺序的优先级.通过问卷调查和两个实验,对代码坏味处理顺序优先级进行了初步验证.

摘要:网构软件是开放网络环境中软件系统基本形态的一种抽象,其信任关系本质上是最复杂的社会关系之一.为了增强信任演化模型的自适应性,提高预测的准确性以及有效地抑制自私节点的产生,结合差异化服务和演化博弈理论,提出了一种符合开放网络特征的信任演化模型:(1) 建立基于差异化服务的实体全局收益函数,以增强信任演化模型的自适应性;(2) 以演化博弈理论作为分析工具,借助Wright-Fisher 模型的特点,提出了一种Wright-Fisher 多策略信任演化模型,以增强对信任演化预测的准确性;(3) 根据“公平规范”原则建立了基于博弈的激励机制,激励信任策略的演化,从而有效地抑制自私节点的产生.实验结果表明:该模型能够更准确地反映开放网络中实体信任行为的复杂性特点;在激励机制的作用下,网构软件的信任演化能够更快地达到稳定状态,从而有效地提高网络的效率,使网构软件系统的信任收益达到最优.

摘要:介绍了基于递归规则的网络声明式语言Netlog 的语法和分布式不动点语义,定义了强良好的程序,并证明了强良好的程序的计算结果对有限的消息丢失不敏感.

摘要:与纯文本文档集相比,使用语义标签标注的半结构化的XML 文档集,有助于信息检索系统更好地理解待检索文档.同样,结构化查询,比如SQL,XQuery 和Xpath,相对于纯关键词查询更加清晰地表达了用户的查询意图.这二者都能够帮助信息检索系统获得更好的检索精度.但关键词查询因其简单和易用性,仍被广泛使用.提出了XNodeRelation 算法,以自动推断关键词查询的结构化信息(条件/目标节点类型).与已有的推断算法相比,综合了XML 文档集的模式和统计信息以及查询关键词出现的上下文及其关联关系等推断用户的查询意图.大量的实验验证了该算法的有效性.

摘要:针对高维数据近似最近邻查询,在过滤-验证框架下提出了一种基于学习的数据相关的c-近似最近邻查询算法.证明了数据经过随机投影之后,满足语义哈希技术所需的熵最大化准则.把经过随机投影的二进制数据作为数据的类标号,训练一组分类器用来预测查询的类标号.在此基础上,计算查询与数据集中数据对象的海明距离.最后,在过滤后的候选数据集上计算查询的最近邻.与现有方法相比,该方法对空间需求更小,编码长度更短,效率更高.模拟数据集和真实数据集上的实验结果表明,该方法不仅能够提高查询效率,而且方便调控在查询质量和查询处理时间方面的平衡问题.

摘要:提出了一种并行连接查询处理算法CoLocationHashMapJoin(CHMJ).首先,设计了多副本一致性哈希算法,将具有连接关系的表根据其连接属性的哈希值在机群中进行分布,在提升了连接查询处理中数据本地性的同时,保证了数据的可用性;其次,基于多副本一致性哈希数据分布,提出了HashMapJoin 并行连接查询处理算法,有效地提高了连接查询的处理效率.CHMJ 算法在腾讯公司的数据仓库系统中进行了应用,结果表明,CHMJ 连接查询的处理效率比Hive 系统提高了近5 倍.

摘要:研究了一种基于时态编码和线序划分的时态XML 索引机制.首先,提出一种基于扩展先序编码的时态编码方案,通过该编码可确定结点间的结构关系;其次,在深入分析时间区间关系的基础上引入线序划分的概念,并讨论了获取线序划分的算法;然后,建立了整合路径结构信息和时态约束信息的时态结构摘要,并在此基础上建立了时态XML 索引结构——TempSumIndex,同时研究了基于TempSumIndex 的时态XML 查询和增量式更新算法;最后,对TempSumIndex 和现有时态XML 索引技术的基本性能进行了详细的实验评估.实验结果表明,TempSumIndex 具有更为优越的性能.

摘要:分布式拒绝服务(distributed denial of service,简称DDoS)攻击是当今互联网的重要威胁之一.基于攻击包所处网络层次,将DDoS 攻击分为网络层DDoS 攻击和应用层DDoS 攻击,介绍了两类攻击的各种检测和控制方法,比较了处于不同部署位置控制方法的优劣.最后分析了现有检测和控制方法应对DDoS 攻击的不足,并提出了DDoS 过滤系统的未来发展趋势和相关技术难点.

摘要:探讨一种全局式的声明式传感器网络开发模式,将全局式的声明式网络程序编译为分布式程序,再交给网络节点的虚拟机执行.因此,开发者只需声明网络全局的功能,而无须处理网络的分布式计算过程以及底层细节.

摘要:可信计算的链式度量机制不容易扩展到终端所有应用程序,因而可信终端要始终保证其动态运行环境的可信仍然较为困难.为了提供可信终端动态运行环境客观、真实、全面的可信证据,设计并实现了一个基于可信平台模块(trusted platform model,简称TPM)的终端动态运行环境可信证据收集代理.该代理的主要功能是收集可信终端内存、进程、磁盘文件、网络端口、策略数据等关键对象的状态信息和操作信息.首先,通过扩展TPM 信任传递过程及其度量功能保证该代理的静态可信,利用可信虚拟机监视器(trusted virtual machine monitor,简称TVMM)提供的隔离技术保证该代理动态可信;然后,利用TPM 的加密和签名功能保证收集的证据的来源和传输可信;最后,在Windows 平台中实现了一个可信证据收集代理原型,并以一个开放的局域网为实验环境来分析可信证据收集代理所获取的终端动态运行环境可信证据以及可信证据收集代理在该应用实例中的性能开销.该应用实例验证了该方案的可行性.

摘要:针对无线传感器网络的不同应用需求,将其分为4 种类型:节点平行于目标平面的延时覆盖、无延时覆盖、节点位于目标平面中的延时覆盖及无延时覆盖.综合考虑节点感知区域和可能感知区域等因素,为每种应用构建了不同的感知模型.围绕不同的感知模型,针对节点部署方式和部署个数进行了分析,并且对结果进行了仿真.结果表明,所提出的的感知模型和部署个数的估计结果正确,且更符合实际应用需求.

摘要:在最小割理论基础上提出了最小割多路径(min-cut multi-path,简称MCMP)路由算法,为流量请求选取少量关键路径,并在这些路径间均衡流量,在获得方法易实现性的同时能够有效地控制网络瓶颈链路拥塞.通过实际流量数据在北美和欧洲骨干网络中的实验,对比常用的OSPF(open shortest path first)路由算法和模型中的多路径路由算法,MCMP 路由算法可降低拥塞链路负载分别达到41%和20%以上.

摘要:消除伪造源地址分组是互联网安全可信的内在要求.基于路由的分布式分组过滤具有良好的效果,但是目前对其有效性缺乏严密的理论分析.基于域间路由传播和互联网拓扑的分层特征,建立路由传播数模型和理想AS 图模型,以此为工具分析了基于域间路由的最大过滤和半最大过滤有效性.结论印证并从理论上解释了前人研究中的实验结果.最大过滤能够消除绝大多数的伪造分组,虽然无法达到100%,但可以将伪造成功的自治系统数量限制为互联网AS路径的平均长度.在理想AS图上,半最大过滤与最大过滤的有效性相同,但是存储和计算开销要小很多,为实际中部署半最大过滤提供了理论依据.理论模型分析揭示了基于域间路由的分布式分组过滤的内在优缺点,有助于设计辅助措施和在整个互联网全面而合理地部署.

摘要:提出一种基于取整划分函数的k 匿名算法,并从理论上证明该算法在非平凡的数据集中可以取得更低的上界.特别地,当数据集大于2k² 时,该算法产生的匿名化数据的匿名组规模的上界为k+1;而当待发布数据表足够大时,算法所生成的所有匿名组的平均规模将足够趋近于k.仿真实验结果表明,该算法是有效而可行的.

摘要:针对程序语言信息流安全领域的现有机密消去策略,提出了一种基于下推系统可达性分析的程序信息流安全验证机制.将存储-匹配操作内嵌于对抽象模型的紧凑自合成结果中,使得对抽象结果中标错状态的可达性分析可以作为不同机密消去策略下程序安全性的验证机制.实例研究说明,该方法比基于类型系统的方法具有更高的精确性,且比已有的自动验证方法更为高效.

摘要:基于证书加密方案通常将消息空间限制于某个特殊的群并且不适合大块消息加密.为了解决这一问题,将带标签的密钥封装机制引入到基于证书系统中,提出了带标签的基于证书密钥封装机制的形式化定义及安全模型.在此基础上构造了一个带标签的基于证书密钥封装方案,并证明了该方案在随机预言模型下是自适应选择密文不可区分的.

摘要:近年来,虚拟化技术成为计算机系统结构的发展趋势,并为安全监控提供了一种解决思路.由于虚拟机管理器具有更高的权限和更小的可信计算基,利用虚拟机管理器在单独的虚拟机中部署安全工具能够对目标虚拟机进行检测.这种方法能够保证监控工具的有效性和防攻击性.从技术实现的角度来看,现有的研究工作可以分为内部监控和外部监控.根据不同的监控目的,详细地介绍了基于虚拟化安全监控的相关工作,例如入侵检测、蜜罐、文件完整性监控、恶意代码检测与分析、安全监控架构和安全监控通用性.最后总结了现有研究工作的不足,并指出了未来的研究方向.这对于从事虚拟化研究和安全监控研究都具有重要意义.

摘要:提出了一种面向仿真组件的并行联邦成员框架,以解决基于HLA(high level architecture)复杂仿真系统联邦成员开发的问题,并提升多核处理器环境下联邦成员的运行性能.并行联邦成员框架通过仿真组件的组合、装配来构建联邦成员.通过仿真引擎管理、数据分发管理、对象管理、组件管理服务和负载平衡功能,并行联邦成员框架为仿真模型构建了一个多核的并行执行环境,并确保并行成员能与RTI 正确交互.通过实验来研究并行成员框架引入的额外开销,并比较并行成员和普通成员的性能.实验结果表明,并行框架能够充分利用多核处理器的计算能力来减少仿真系统运行时间,提高系统性能.

摘要:提出了一种基于硬件虚拟化技术的单向隔离执行模型.在该模型中,安全相关的应用程序可以根据自身需求分离成宿主进程(host process)和安全敏感模块(security sensitive module,简称SSM)两部分.隔离执行器(SSMVisor)作为模型的核心部件,为SSM 提供了一个单向隔离的执行环境.既保证了安全性,又允许SSM 以函数调用的方式与外部进行交互.安全应用程序的可信计算基(trusted computing base,简称TCB)仅由安全敏感模块和隔离执行器构成,不再包括应用程序中的安全无关模块和操作系统,有效地削减了TCB 的规模.原型系统既保持了与原有操作系统环境的兼容性,又保证了实现的轻量级.实验结果表明,系统性能开销轻微,约为6.5%.

摘要:Lopez 等学者求解出基于单调速率算法和首次适应分派策略的多处理器实时任务可调度性判定边界.该边界在所有O(m)复杂度的判定边界中是最优的.基于Bini 等学者针对单处理器提出的双曲线可调度性判定方法,给出了一种多处理器实时任务可调度性判定边界.新边界在相当数量的利用率分布下明显优于已有边界.新边界与已有边界具有相容性,所以虽然新边界无法在所有情况下超越已有边界,但在实际应用中可联合两种边界进行判定,在不增加计算复杂度的同时全面提高可调度任务集的数量.