软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2011年第11期杂志 文档列表

软件学报杂志理论计算机科学

鸽巢公式的一些性质2553-2563

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

基于文法分支覆盖的短句子生成算法2564-2576

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

软件学报杂志系统软件与软件工程

基于编档的体系结构视图冲突检测方法2577-2592

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

一种服务Agent的可信性评估方法2593-2609

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

监控使能的分布式软件系统构造方法2610-2624

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

基于事件确定有限自动机的UML2．0序列图描述与验证2625-2638

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

面向方面的计算误差处理技术：实例研究与评估2639-2651

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

事务控制的面向服务系统的动态更新协调2652-2667

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

基于有限自动机的多层次构件行为匹配模型2668-2683

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

BPEL流程建模中的交叠模式分析与转换2684-2697

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

Web服务组合功能与QoS的形式化统一建模和分析2698-2715

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

基于对象的软件行为模型2716-2728

摘要：以传统有限自动机（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）,其实验和分析结果表明,该模型可以有效地检测基于控制流的攻击、模仿攻击以及针对数据语义的攻击,并给出了该工具的性能开销.

融合安全的网格依赖任务调度双目标优化模型及算法2729-2748

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

基于率的构件软件可靠性过程仿真2749-2759

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

软件学报杂志模式识别与人工智能

复杂分布数据的二阶段聚类算法2760-2772

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

查询依赖的有序多超平面排序学习模型2773-2781

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

软件学报杂志计算机网络与信息安全

可信可控网络中的QoS资源控制模型2782-2794

摘要：基于前期工作——可信可控网络体系结构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网络具有更高的可控性

基于时延的Flash Crowd控制模型2795-2809

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