摘要:由鸽巢原理定义的鸽巢公式PH_nⁿ⁺¹ 是著名的消解难例之一,研究该公式的结构和性质有助于其他难例的构造.证明了PH_nⁿ⁺¹ 是一个极小不可满足公式,根据其极小不可满足性,给出了最大可满足真值指派的两种标准形式,Haken 关于PH_nⁿ⁺¹ 的难解证明用到了其中一种标准形式.公式PH_nⁿ⁺¹ 具有良好的子结构同构性质,如果DPLL 算法中允许使用同构规则,则存在PH_nⁿ⁺¹ 的反驳证明,其复杂性可以降至O(n³).

摘要:提出一种上下文无关文法的句子生成算法.对于给定文法,算法生成一个满足该文法分支覆盖准则的句子集.结合长度控制、冗余消除和句子集规模控制等策略,使得生成的句子较短、无冗余、句子集规模较小.考察了算法在基于文法的软件系统的测试数据生成方面的应用情况.实验结果表明,该算法生成的测试数据具有较强的程序揭错能力,并且能够帮助测试人员提高测试速度.

摘要:软件体系结构由不同的视图组成,每个视图包含不同的体系结构关注点.在软件工程领域中,如何对这些视图进行比对和合并是一项非常重要的研究工作.然而,目前视图比对的主要研究都着眼于视图元素之间的比对,因而并不能有效地发现视图之间的隐含冲突.主要原因是由于不同视图背后隐含着不同的关注点,而关注点之间的冲突并不能显式地在视图中表现出来,因此仅作视图元素比对不能发现这种隐含冲突.针对该问题,提出了一种基于编档的体系结构视图隐含冲突检测方法.在该方法中,通过对设计方法进行建模来捕获体系结构关注点和视图之间的关联关系;以软件体系结构文档作为通用平台,通过4 个连续的活动来检测关注点之间的隐含关系;为了支持方法的自动化,就其中出现的关系给出了一套数学定义.

摘要:提出了一个基于服务Agent 的计算框架,并从社交认知的角度建立了一个服务Agent 的信任本体,支持服务Agent 对信任信息进行推理.根据该信任本体,提出一系列基于信任推理的计算规则支持信任值的计算,帮助服务Agent 进行理性的选择决策.案例研究结果表明,该方法能够有效地帮助服务请求方进行信任评价以及服务选择.

摘要:针对开放的网络环境中大型分布式软件的调试、调优、维护和可信演化问题,提出了伴随式的监控使能分布式软件构造方法.基于发布/订阅的分布计算模型,提出了被监控对象的业务逻辑和监控逻辑分离的运行时体系结构;基于面向方面编程思想,提出了监控使能的分布式软件开发方法和工具,降低了监控实施代价,增强了代码的可维护性;基于运行时体系结构,提出了监控系统的动态可定制部署方法.监控使能的分布式软件构造方法能够在开发时控制功能代码和非功能代码的纠结,尽可能地降低软件编程人员的代码维护难度;能够在部署时保证监控系统和被监控对象的松耦合;能够在运行时实现监控信息的按需汇聚和按需处理.从而在对系统核心业务的影响尽可能小的前提下.获得对系统运行行为尽可能全面的理解.

摘要:为了确保软件分析与设计阶段UML2.0 序列图模型的可靠性,采用命题投影时序逻辑(propositional projection temporal logic,简称PPTL)模型检测方法对该模型进行分析和验证.提出了事件确定有限自动机(event deterministic finite automata,简称ETDFA),并使用该自动机为序列图建立形式化模型,通过给出的基于ETDFA 的PPTL 模型检测算法得到验证结果.该方法可以在基于Spin 的PPTL 模型检测器的支持下实现.实例结果表明,该方法可以验证序列图的性质并保证其可靠性.

摘要:传统的实现方法通常把误差处理策略与程序的基本功能交织到一起,这会增加程序的耦合度,使得程序难以理解与维护.针对这一问题,提出一种面向方面的解决方案,即将程序的各种误差处理策略封装为方面.为评估该方法的有效性,将一个真实的卫星轨道测算系统中的误差处理策略分别封装为类中的方法和方面,并设计了一系列实验来评估原程序及分别采用两种方式重构后的程序在关注点分离度、耦合度、程序规模及运行时间上的差异.结果实验结果和重构过程中获得的经验可以得出,采用面向方面技术将误差处理功能封装为方面来实现能够有效提高程序的模块化程度和可维护性,并且不会引起程序性能的显著下降.

摘要:就面向服务的分布式系统中多服务动态更新的协调问题,提出基于事务控制的更新协调策略,包括安全更新时机的选择策略、使用2PC(two-phase-commit)协调多服务更新的控制策略.根据更新实施的各步操作时间开销,提出分别采用更新短事务控制基本更新操作(包括创建服务实例、顺序实施运行时状态转换、重定向服务请求和新服务的激活操作)和转换长事务控制多组持久数据转换操作(其中每组持久数据转换由一个相应的短事务控制)的更新实施策略,以期借助于事务的控制机制尽可能高效地保证更新前后系统运行状态的ACID 特性.就事务控制策略的自动实施做了一定的研究工作,包括:根据更新描述脚本自动生成更新短事务操作序列、根据持久数据关联构件的依赖关系分析自动生成各个持久数据转换短事务序列组成的长事务以及对应用事务和各转换事务的序列化处理.最后,通过基于Apache CXF-DOSGi 的原型实现对给出的控制策略进行了可行性验证.

摘要:针对目前基于行为规约匹配的构件获取方面的不足,提出了一种基于有限自动机的多层次的构件行为匹配模型.该模型采用有限自动机对构件的行为进行建模,借鉴图论中图匹配的思想,提出了6 种行为匹配关系:等价行为匹配、扩展行为匹配、相容行为匹配、包含行为匹配、弱包含行为匹配和弱相容行为匹配.分析了这些行为匹配关系之间的蕴涵关系,并给出各种行为匹配关系的判定算法和相应的适配方法.基于这些算法,提出了一种通用的行为匹配判定方法,以此来减少后继构件适配和组装的复杂性.所提出的匹配模型为基于行为的构件获取提供了有利的技术支持.

摘要:由图形化流程建模语言生成可执行的业务流程语言(business process execution language,简称BPEL)时,对于源模型中顺序与并发结构交织的情况(称为交叠模式),传统的复制相关活动方法缺少系统分析及形式化描述.针对这一现状,提出基于工作流网的UML 活动图生成BPEL 方法,以自由选择工作流网作为活动图的理论基础,利用活的、有界的自由选择网系统的合成规则,定义合理的自由选择工作流网中的两种交叠模式,针对其中一种给出复制相关活动的形式化转换方法,并借助Petri 网的并发正则表达式证明转换等价性,说明另一种交叠模式中复制相关活动方法的适用范围.针对BPEL 流程建模及图形化流程语言生成块状语言过程中的交叠模式转换问题,给出形式化的描述与解决方法.

摘要:进程代数是一种适合描述Web 服务组合的形式建模语言,然而同样对QoS 建模和分析的支持不足.在现有进程代数的基础上,提出了一种代价概率进程代数PPPA(priced probabilistic process algebra),给出其语法和语义,证明其具有功能、概率和代价的统一建模和分析能力.给出了基于PPPA 统一建模和分析Web 服务组合功能和QoS 的方法.实例建模和分析了Web 服务组合的功能、可靠性、性能和代价,其结果表明,PPPA 可以有效地支持Web 服务组合功能和QoS 的形式化统一建模和分析.

摘要:以传统有限自动机(finite state automata,简称FSA)为基础,从系统调用参数中解析出系统对象,提出了一种基于系统对象的软件行为模型(model of software behavior based on system objects,简称SBO).该模型的行为状态由软件所关联的所有系统对象表示,从而赋予状态的语义信息,解决了不同行为迹中PC(program counter)值的语义不相关问题;同时,该模型可以对抗系统调用参数的直接和间接修改,从而可以检测基于数据语义的攻击.最后,实现了基于SBO 的软件异常检测原型工具(intrusion detection prototype system based on SBO,简称SBOIDS),其实验和分析结果表明,该模型可以有效地检测基于控制流的攻击、模仿攻击以及针对数据语义的攻击,并给出了该工具的性能开销.

摘要:为了解决异构网格环境下依赖任务调度问题面临的安全威胁,综合考虑网格资源节点的固有安全性和行为安全性,分别构建了一个网格资源节点身份可靠性度量函数和行为表现信誉度评估策略.同时,为了确立任务安全需求与资源节点安全属性之间的隶属关系,定义了安全效益隶属度函数,从而建立一个网格任务调度的安全融合模型.以此为基础,提出一个时间-安全驱动的双目标优化网格依赖任务调度模型.为了求解该模型,处理任务间约束关系时引入深度值和关联耦合度的排序定义,再结合网格任务调度问题的具体特点,重新定义和设计新的粒子进化方程.同时,基于均匀分布向量和粒子浓度定义了选择策略,从而提出一种双目标优化的网格依赖任务调度粒子群进化算法,并运用概率论的有关知识证明算法的收敛性.最后,对所提出的离散粒子群进化算法进行了多角度分析和大规模仿真实验,其仿真结果表明,该算法与同类算法相比,不仅具有较好的收敛速度和单目标优化性能,而且在任务调度长度和安全满意度方面具有更好的双目标优化综合性能.

摘要:与传统的基于模型的构件软件可靠性分析方法相比,基于率的仿真方法由于可以灵活地跟踪软件动态失效过程,近年来开始用于分析构件软件的可靠性过程.但是,目前已经提出的仿真方法对构件软件测试中的故障排除过程做了过分简化的假设,而未能描述软件系统实际的可靠性过程.针对这个问题,提出了一种仿真方法.该方法采用一个混合排队模型建模故障排除过程,其中考虑到了排错策略和排错资源的局限性问题.在此基础上开发出仿真过程,实现对构件软件可靠性过程的仿真.实验结果表明了该仿真方法的有效性.

摘要:提出了一种用于复杂分布数据的二阶段聚类算法(two-phase clustering,简称TPC),TPC 包含两个阶段:首先将数据划分为若干个球形分布的子类,每一个子类用其聚类中心代表该类内的所有样本;然后利用可以处理复杂分布数据的流形进化聚类(manifold evolutionary clustering,简称MEC)对第1 阶段得到的聚类中心进行类别划分;最后综合两次聚类结果整理得到最终聚类结果.该算法基于改进的K-均值算法和MEC 算法.在进化聚类算法的基础上引入流形距离,使得算法能够胜任复杂分布的数据聚类问题.同时,算法降低了引入流形距离所带来的计算量.在分布各异的7 个人工数据集和7 个UCI 数据集测试了二阶段聚类算法,并将其效果与遗传聚类算法、K 均值算法和流形进化聚类算法做了比较.实验结果表明,无论对于简单或复杂、凸或非凸的数据,TPC 都表现出良好的聚类性能,并且计算时间与MEC 相比明显减少.

摘要:针对当前基于支持向量机的排序学习方法训练时间长以及不考虑查询之间差异、模型单一的问题,提出一种查询依赖的有序多超平面排序学习模型.根据不同查询,利用其对应训练数据所属等级之间的序关系构建多个超平面.此外,提出了一种加权表决方法对多个超平面的排序列表进行聚合,根据各超平面的排序精度赋予其不同权重,计算最终排序结果.在标准数据集LETOR OHSUMED 上对所提出的模型性能进行了综合评测,并与相关排序模型进行了对比分析.实验结果显示,所提出的模型排序性能有较大提升.同时,训练时间明显缩短.

摘要:基于前期工作——可信可控网络体系结构TCNA(trustworthy and controllable network architecture),提出了一种QoS 资源控制模型(resource control model for QoS,简称RCMQ).该模型从网络可控角度将QoS 控制分为4层: QoS 决策层面、QoS 观测层面、QoS 接口层面和QoS 资源层面,模型部署包括独立集中的域内控制和一致性分布式控制.RCMQ 模型闭环控制结构保证了QoS 控制的有效性,而独立集中的QoS 决策层面使得模型具有可扩展性.最后,通过仿真实验验证了RCMQ 资源控制模型与InterServ 模型相比,能够提供更为稳定的QoS 传输,并且极大地减少了QoS 状态维护,同时也从侧面说明可信可控网络体系比传统TCP/IP 网络具有更高的可控性.

摘要:提出了一种session 级别的flash crowd 控制策略SGAC(session-granularity admission control),将session 控制粒度和request 控制粒度相结合,采用请求平均返回时延作为检测和控制的依据.对session 采取一旦接受就完成的策略,在实现对服务器过载控制的同时,保护用户session 的完整性,并能自动调节新session 的准入速率,以提高服务器利用率.采用真实HTTP Log 进行模拟,结果表明,SGAC 方法能够有效控制服务器过载,保护session 的完整性,提高服务器利用率,降低接入端路由器计算开销,保护有价值的交易session.

摘要:在P2P 网络中,基于衰落Bloom Filter 的弱状态路由算法试图将每条查询消息沿着成员资格信息量最强的方向传递,并最终以较低的传输代价和传输时延确保较高的查准率.衰落Bloom Filter 在传递过程中存在严重的多径叠加和噪音问题,这直接导致查询消息会以很高的概率沿着错误的方向传播,甚至会退化为泛洪路由算法.为了解决这一挑战性难题,提出了DWalker 这种基于衰落Bloom Filter 的高效弱状态路由算法.DWalker 基于有向随机网络,采用指数衰落Bloom Filter 来发布和传播每个节点共享资源的信息,且其最大传播距离小于网络中任意两点之间距离的期望值,从而有效抑制了衰落Bloom Filter 在传播过程中的多径叠加问题.DWalker 采用多个Bloom Filter 而不是单个Bloom Filter 来表达一项路由条目,在单个Bloom Filter 的错误发生概率达到设计上限时,可按需动态增加新的Bloom Filter,以将更多资源对象信息纳入到当前路由条目中.DWalker 仅根据当前节点的各项路由条目中值为1 的比特位所占的最大比例,以及查询消息在正确转发方向对应的路由条目中对应比特位中值为1 的个数的临界值,就能使进入目标对象传播范围内的查询消息以较高的概率辨认出正确的路由方向.理论分析和实验结果表明,DWalker 能够以较低的查询消息代价、较小的路由条目存储开销以及较短的查询时延,使绝大多数查询消息沿正确方向转发,从而获得较高的查准率.

摘要:通过构造不可延展的、可提取的且是弱模拟可靠的陷门承诺体制,以及相应的平滑投射Hash 函数簇,设计了一个高效的通用可组合(universal composable,简称UC)安全的两方口令认证密钥交换(password authenticated key exchange,简称PAKE)协议,并在静态腐化模型下给出了严格的安全性证明.该协议使得PAKE 协议在UC框架下达到了最优的两轮.与已有的协议相比,该协议避免了零知识证明协议的使用,在保持计算复杂度相当的前提下有效地提高了通信效率.

摘要:针对成批数据在无线广播过程中发生丢包后的重传策略,利用网络编码技术,研究尽可能多地减少重传次数的方法.首先通过矩阵及向量的运算给出了待重传数据满足编码条件的代数表达形式,再根据关联矩阵构造相应的图,最后通过图论中的最佳匹配理论给出了一种寻找编码机会的优化算法.此算法中不但能够找出最多的两两编码机会,而且还考虑了将尽可能多的数据包编在一起的可能性,从而尽可能地减少了重传次数,实现了编码的优化,有效提高了网络带宽效率和吞吐量.

摘要:给出了一个无双线性对的无证书两方密钥协商方案,并演示了这些不安全无证书方案存在的攻击.只要每方至少有1 个未泄露的秘密值,该方案在最强的安全模型下就是安全的.即使密钥生成中心知道双方的临时私钥或显示双方的秘密值/替换公钥(但不能同时),但只要计算Diffie-Hellman 假设成立,该方案在随机预言机模型下也被证明是安全的.该方案消除了对运算,与其他无证书密钥协商方案相比,该方案是己知无证书安全协商方案中计算复杂度最低的.该方案尤其适合于带宽受限的通信环境中使用,如Ad Hoc 网络、无线传感器网络等.