摘要:Software Process Workshop (SPW 2005) was held in Beijing on May 25-27, 2005. This paper introduces the motivation of organizing such a workshop, as well as its theme and paper gathering and review; and summarizes the main content and insights of 11 keynote speeches, 30 regular papers in five sessions of "Process Content", "Process Tools and Metrics", "Process Management", "Process Representation and Analysis", and "Experience Reports", 8 software development support tools demonstration, and the ending panel "Where Are We Now? Where Should We Go Next?".

摘要:虽然设计模式有利于软件的重用,但当设计模式实例化时,存在模式的重叠、可追踪性以及模式代码难于重用等问题.提出一种基于角色的设计模式的建模和实现方法,在设计和实现两个层面上解决上述问题.该方法把设计模式的角色作为独立的建模元素,在应用程序类和角色间导入RoleOf关系,使应用逻辑和模式逻辑完全分离,从而提高其重用性.使用UML的标准扩充机制,给出了RoleOf关系的元模型和语义,以及标识模式信息的构造型和标记值,以此解决模式的重叠和可追溯性等问题.通过对Java语言进行扩充(称为Rava),实现了应用逻辑和模式逻辑的动态绑定.该方法较好地解决了设计模式实例化时的模式重叠和可追踪性问题,提高了模式逻辑的可重用性,对运用设计模式开发软件有一定的指导作用.

摘要:由于简洁、直观的表达能力,Statecharts被用于许多反应系统的行为建模.Statecharts可表示不同抽象层次的系统行为,因而可用来表示逐步求精建模中各步的结果.但对于求精过程中下层是否保持了上层的语义、所建模型是否满足某些性质的问题,却难以在其自身的框架下进行讨论.在这方面,形式化语言XYZ/E可与其互补.XYZ/E是一种可执行线性时序逻辑语言,既可表示系统的性质,又可表示系统的行为.递归地在基本迁移系统上解释Statecharts语义,用XYZ/E公式表示它的时序语义.这一语义是模块级可组合的.求精过程的语义保持,可直接从语义定义得到保证.Statecharts所描述的系统行为模型和性质在同一个逻辑中表示,因此,系统行为是否满足所需性质的问题可由逻辑蕴涵式表示.

摘要:网构软件的构建依赖于对开放协同环境中各种异构的、自治的软件服务实体间的有效协同.Internet的开放性与动态性,使得对于诚实的、具有可靠服务质量协同实体的选择难度较大,难以确保网构软件的可信性.软件实体间的信任关系对于保障网构软件的可信性具有重要的指导意义.软件实体间的信任关系通常随协作的进行而不断变化,但现有的信任模型缺乏对实体间信任关系的自动形成与更新的支持,从而无法刻画信任关系的动态性.针对该问题,提出了一个适用于网构软件的信任度量及演化模型.该模型不仅对信任关系度量过程和信任信息传递及合并过程进行了合理抽象,而且还提供了一种合理的方法,用于促进协同实体间信任关系的自动形成与更新.该模型有助于解决开放环境下网构软件的可信性问题.

摘要:随着硬件设备和软件技术的发展,国内外开展了大量基于Post-WIMP界面的新型交互技术的研究.面对多种交互设备以及使用环境,在界面设计的过程中,根据上下文选择适当的交互组件或技术,并有效地进行组合与评估,成为构造Post-WIMP界面的关键问题.将界面设计与应用语义分离,使设计者能够灵活地置换各种交互技术.通过对Post-WIMP界面交互过程与界面设计层次的分析,建立起以交互为中心的分层Post-WIMP界面模型,将交互的各个层次进行分离.在模型的基础上,描述一个了Post-WIMP界面生成工具.借助该工具,设计者能够在设计过程中方便地引入新的交互技术,并能在最终的软件系统中加以灵活应用,从而可以快速、有效地进行界面原型实现和迭代评估.应用实例表明,Post-WIMP模型的建立以及生成工具的实现,有利于设计者确定设计方案及对方案的整体评估.

摘要:面向对象的软件设计改进是增强系统的可扩展性、使之适应可能的需求变化的一种有效手段.提出一种基于CBR(case based reasoning)和微体系结构反模式的设计改进方法.该方法形式化地定义了在微体系结构层中不灵活的设计结构和相应的重构方案的描述方法,研究了它们在事例库中的组织和索引机制.根据基于事例的推理技术的4R过程,提出了类图、顺序图、质量要素和语义约束的相似性度量方法,描述了在给定设计中识别反模式及其实例,并在此基础上,用高质量的设计方案进行替代的几种算法.以该方法为依据,进一步介绍了设计改进支撑系统--CBDIT(CBR based design improving tool)的体系结构的设计.

摘要:共代数方法是近几年来理论计算机科学的研究热点之一,在并行计算模型、自动机及面向对象技术的理论基础方面有着广泛的应用.以范畴理论为工具讨论子共代数的性质,特别是集合范畴上的子共代数的性质,证明了集合范畴上的子共代数都是正则子共代数.进一步利用共同余共关系与子共代数之间的对应,给出了集合范畴上共生成子共代数的一种构造方式.

摘要:目前的模型检测方法中,有一种方法是基于自动机来实现的.具体做法是:将抽象出的系统模型用Büchi自动机来表示,将需要验证的性质用LTL(linear temporal logic)公式来表达;然后将LTL公式取反后转化为Büchi自动机,并检查这两个自动机接受语言之间的包含关系.有一类LTL公式转化为Büchi自动机的算法是:在计算过程中,首先得到一个标注在迁移上的扩展Büchi自动机(transition-based generalized Büchi automaton,简称TGBA),然后把这种扩展Büchi自动机转换成非扩展的Büchi自动机.针对这类转换算法,根据Büchi自动机接受语言的特点,重新定义了基于迁移的扩展Büchi自动机的求交运算,减少了需要复制的状态个数,使转换后的自动机具有较少的状态.测试的结果表明:对随机产生的公式,新算法相对于以往的算法有明显的优势.

摘要:对二维logistic映射的动力学研究有助于认识和预测更复杂的高维非线性系统的性态.利用解析计算和实验分析相结合的方法揭示出:(1) 参数空间中二维logistic映射发生第一次分岔的边界方程;(2) 二维logistic映射可按倍周期分岔和Hopf分岔走向混沌;(3) 二维logistic映射的吸引盆中周期和非周期区域之间的边界是分形的,这意味着无法预测相平面上点运动的归宿;(4) Mandelbrot-Julia集的结构由控制参数决定,且它们的边界是分形的.

摘要:数据流滑动窗口连接聚集连续查询(简记J-A查询)是经常使用的一类查询.这类查询的直观处理方法是创建查询操作树,以流水线的方式计算查询结果.这种方法需要在主存中保存滑动窗口连接的结果,查询处理的主存空间开销为O(α×β),其中(,(为参加连接两个滑动窗口的大小.在数据流的查询处理中,内存是最重要的计算资源.提出了两种滑动窗口J-A连续查询处理算法--IC算法和TC算法,使得查询处理的空间开销降为Ο(α+β).理论分析和实验结果表明,所提出的算法具有更高的效率.

摘要:首先对按元素划分安全级的多级数据库上由函数依赖(FD)和多值函数依赖(MVD)引起的推理问题进行了研究,所提出的推理控制算法在很大程度上提高了数据的可用性.为进一步有效防范推理所导致的敏感信息泄露,给出了基于视图的推理控制方法.该方法能够处理多视图合谋带来的安全问题.最后给出了视图依赖基划分原理,它是以后有关视图推理控制的基础.

摘要:数据模型是XML数据管理领域研究的核心问题之一.现有的数据模型在表达XML数据库复杂的数据结构和操作方面仍有不足.以映射为基础,提出了一种新的数据模型.该数据模型给出了XML数据库复杂的数据结构和语义的精确定义,并提供了数据结构上操作代数的定义,包括路径表达式操作和数据维护操作.该数据模型已应用于一个基于XML的信息集成系统中.事实表明,它能够有效地支持XML数据管理的应用.

摘要:主要研究XML文档的并行数据分片策略,以便能够并行处理XML查询.为了描述XML数据分片,提出了媒介节点的概念.一组媒介节点的集合可以将一棵XML数据树分割成一棵根树和一组子树的集合:根树将在所有站点中复制;而子树集合则可以根据用户查询的工作负载被均匀地分片到各个站点中.对于同一棵XML数据树,会有很多种媒介节点的集合;而不同的媒介节点集合会产生不同的数据分片结果.然后,依据各个数据分片中的用户查询工作量是否均衡,来衡量一个分片的好坏.选择一组最佳的媒介节点集合是一个NP-hard问题.为了解决此问题,设计了一组启发式优化规则.基于这一思想,提出并实现了一种基于媒介节点的XML数据分片算法WIN(workload-aware intermediary nodes data placement strategy).大量实验结果证明:WIN算法的性能要优于以往的并行XML数据分片策略.

摘要:查询扩展是解决信息获取领域中用词歧义性问题的关键技术,并被广泛应用于搜索引擎中,获得了巨大的成功.然而,由于P2P(peer-to-peer)系统是一个分散的、动态的系统,在P2P环境下进行有效的查询扩展具有一定的挑战性.首先,利用查询与文档的关联关系构建了LEM(local expansion method)查询扩展方法;然后,基于查询与文档用词的直接关联,提出了HEM(history_based expansion method)查询扩展方法.在此基础上,提出了一种基于查询扩展的混合P2P环境下的搜索算法.实验及分析结果表明,查询扩展及其搜索算法能够极大地提高搜索的效果.

摘要:在无线传感器网络环境中,观察者感兴趣的是由传感器网络监测得到的与时间-空间相关的事件,而不是传感器本身或者大量无关的观察数据.观察者会经常提出与事件相关的时-空查询,例如:"网络覆盖的某地理区域R中10:00～11:00发生了哪些事件?".由于每个传感器节点只有有限的能量,因此,研究能量有效性的时-空查询处理算法成为一个重要的研究课题.给出了一种以数据为中心的时-空查询处理算法.针对3种不同的存储策略:以数据为中心的存储、外部存储和节点本地存储,分析比较了节点的能量消耗.系统地研究了在3种不同的数据存储策略下,事件发生的概率,节点密度,事件类型数目,查询数目,时-空查询地理区域的大小以及时-空查询时间窗口的大小对节点能量消耗的影响.理论与实验结果表明,在多数情况下,这种以数据为中心的时-空查询处理算法的能量消耗少于基于外部存储和本地存储的时-空查询处理算法.

摘要:以往在数据立方体上实现的联机聚集往往需要附加空间来存储联机聚集估算所需要的信息,极大地影响了数据立方体的存储和维护性能.提出了基于QC-Tree的用于范围查询处理的联机聚集PE(progressively estimate)算法以及它与简单聚集算法相结合的混合聚集算法HPE(hybrid progressively estimate);还提出了一种能够同时处理多个范围查询的联机聚集算法MPE(multiple progressively estimate).与以往联机聚集算法不同,这些算法不需要任何附加空间,而是利用QC-Tree自身保存的聚集数据和语义关系来估算聚集结果.由于QC-Tree是一种极为高效的数据立方体存储结构,因此能够以较理想的性能实现数据立方体上的联机聚集.对算法的分析和实验结果表明,所提出的算法具有较好的性能.

摘要:多协议标记交换(multiprotocol label switching,简称MPLS)技术运用显式的标记交换路径(label switching path,简称LSP),使得互联网上流量工程的部署变得简单和高效.因此,LSP选路算法成为MPLS流量工程中的核心和热点问题.深入剖析了LSP选路算法中的最小干扰选路算法(minimum interference routing algorithm,简称MIRA)的关键思想,综述了对MIRA的各种改进方案,并依据其实现方案将现有主要最小干扰选路算法分为4类:关键链路的重新定位类、利用流量特征信息类、增加准入控制类和解决多服务质量受限类.在分析每类算法核心思想的基础上,阐述了各类的典型算法,讨论了每种算法的优点和适用环境,剖析了其中存在的主要问题,并对它们进行了综合对比.最后指出了最小干扰选路算法进一步的研究方向.

摘要:基于EPFTS(ethernet-like physical frame timeslot switching)交换技术,提出了一种新型调度算法TWFS(timeslot weighted fair scheduling),可实现于EPFTS(ethernet-like physical frame timeslot switching)交换节点,满足SUPANET(single physical layer user-data platform architecture network)网络中具备QoS(quality of service)保障能力的快速数据转发的需要.通过分析两类典型的调度机制iSlip(iteration round-robin match with slip)和BvN-switch(Birkhoff-von neumann switch)的优缺点,TWFS利用类似iSlip的迭代机制,以交换节点输入输出端口对上预定的时槽总数作为数据转发的度量权值(优先权),克服了BvN-switch对负载变化反应慢的缺点,同时又使算法时间复杂度保持在与iSlip相同的级别O(log₂N).仿真实验结果表明,TWFS算法在算法有效性、公平性和实现复杂度之间取得了很好的平衡,因而特别适合于SUPAENT中的EPFTS高速交换节点.

摘要:无线传感器网络中的"瓶颈节点"是指那些由于随机部署的原因而不得不成为连接两个或多个区域的孤立的节点.相对于其他节点,这类节点对网络的生存期有着更大的影响.如何找出这些"瓶颈节点"在图论中是一个找到最小割集的问题.基于实际部署的可行性,提出了一个新的"准瓶颈节点"的概念,它对网络具有与"瓶颈节点"类似的影响,但是可以很容易地通过分布式算法找出来.通过分析和仿真,证明了"准瓶颈节点"对网络行为(包括能量消耗速率、丢包率)的巨大影响.最后,提出了一种分布式算法来发现这些节点,并提出了两种有效的解决思路来减小它们的不利影响.

摘要:考虑网络节点的流守恒特性,网络流量的有效监测问题可抽象为求给定图G(V,E)的最小弱顶点覆盖集的问题和基于流划分的最小弱顶点覆盖集的问题,这是NP难的问题.首先分析了弱顶点覆盖集的约束关系,并给出了问题的整数规划形式.然后利用原始对偶方法构造了求解最小弱顶点覆盖集的近似算法,并分析了算法的比界为2.进一步分析了求解基于最大流划分的最小弱顶点覆盖集的近似算法.

摘要:在诸如文件共享的P2P(peer-to-peer)网络中,节点不可靠的自主行为严重影响了P2P服务的可用性.而目前,主流的全分布P2P网络在构造拓扑时都没有考虑节点的自主行为特征,节点在拓扑上的地位是对等的.充分考虑了节点构造拓扑的理性,提出了基于节点互惠能力的自适应P2P拓扑构造协议.仿真分析表明,利用该协议构造的拓扑对P2P网络中不同类型的节点具有激励一致性.此外,该网络拓扑与已有同类拓扑相比更有效,且网络开销更小.

摘要:旨在为移动计算中多跳网络链路的研究建立一个计算复杂度较低的通用分析模型,奠定一定的数学研究基础.在已有成果的基础上,将研究的粒度从节点扩展到由若干节点组成的路径,并提出了基于流水排队策略的无线多跳路径容量分析模型.这个模型可以有助于在无线多跳网络中规整地探索网络传输的吞吐能力的状况,可以为研究MANET和Sensor network的传输链路的通信能力的工作提供一种比较高效的计算和分析模式.所得到的多跳环境下的网络容量表达式,计算比较简单,可以用于动态调整系统参数的设计中,在设计QoS路由算法时也是很有裨益的.

摘要:结合传感器网络的节点特性和位置信息,提出了一种基于连通支配集的传感器网络定向传播模型,以及一种基于"域"的分布式数据汇聚模型DDAM(distributed data aggregation model).DDAM把传感器网络按"域"划分来构建连通核,传感节点只需在连通核中寻径,因而可明显减少寻径时间复杂度并且具有更好的分布性;然后在该定向传播与数据汇聚模型基础上,考虑传感器网络的数据特性及小波变换在流数据压缩方面的良好性能,提出了一种基于区间小波变换的混合熵数据压缩方法.理论分析和实验仿真结果表明:对比传统的DC算法-DD路由算法相结合的算法,新算法能对传感器网络中的流数据进行有效压缩,可更大程度地降低传感器节点数据传输的能耗,从而进一步延长整个网络的生命周期.

摘要:针对用于移动通信的可证安全的双向认证密钥协商协议MAKAP给出了一种有效攻击,指出该协议存在安全缺陷,它不能抵抗未知密钥共享攻击.分析了这些安全缺陷产生的原因,并给出了一种改进的协议MAKAP-I.改进后的MAKAP-I协议不但是可证安全的,而且无论从计算开销、通信开销、存储开销以及实现成本等方面,都比原MAKAP协议更高效、更实用.

摘要:在Internet上提供大规模的VoD服务是一项具有挑战性的工作.提出了一种基于P2P(peer to peer)方法的VoD服务体系PeerVoD,它能够以较小的服务器代价实现大规模的VoD应用.PeerVoD中的每个节点均使用定长的FIFO缓存队列来保存其最近所接收到的数据,以便为后续到达的节点提供服务.它具有如下特点:1) 采用分布式控制协议以支持节点的加入和离开,系统具有良好的可扩展性;2) 服务被中断的节点在进行中断恢复时,考虑了节点对目标节目接收的完整性.仿真实验表明:同等条件下,PeerVoD体系在服务器负载、节点加入时被拒绝的概率、网络资源利用率以及节目完整性等性能指标上,均优于同类体系P2VoD.

摘要:安全评估是贯穿信息系统生命周期的重要管理手段,是制定和调整安全策略的基础和前提.只有充分识别系统安全风险,才能有针对性地采取有效的安全防范措施.基于IDS(intrusion detection system)海量报警信息和网络性能指标,结合服务、主机本身的重要性及网络系统的组织结构,提出采用自下而上、先局部后整体评估策略的层次化安全威胁态势量化评估模型及其相应的计算方法.该方法在报警发生频率、报警严重性及其网络带宽耗用率的统计基础上,对服务、主机本身的重要性因子进行加权,计算服务、主机以及整个网络系统的威胁指数,进而评估分析安全威胁态势.实验表明,该系统减轻了管理员繁重的报警数据分析任务,能够提供服务、主机和网络系统3个层次的直观安全威胁态势,使其对系统的安全威胁状况有宏观的了解.而且,可以从安全态势曲线中发现安全规律,以便调整系统安全策略,更好地提高系统安全性能,为指导安全工程实践、设计相应安全风险评估和管理工具提供了有价值的模型和算法.

摘要:描述了基于Objective Caml开发的一个安全协议验证工具SPVT(security protocol verifying tool).在SPVT中,以扩展附加项的类(演算作为安全协议描述语言,以扩展附加项的Horn逻辑规则描述协议攻击者的Dolev-Yao模型,通过一组抽象规则将安全协议的类(演算模型转换为逻辑程序模型,基于安全协议逻辑程序的不动点计算验证安全性质,从安全协议逻辑程序的不动点计算和安全性质的验证过程中构造不满足安全性质的安全协议反例.以简化的Needham-Schroeder公钥认证协议为例,描述了使用SPVT自动验证安全协议的过程,表明了SPVT用于安全协议验证的有效性.

摘要:为了实现网络安全,一个重要的方法是网络用户传送加密和可鉴定的消息.此时,用来加密和鉴定的密钥应该由网络中的用户协商得到.提出了3个基于Weil对的成对密钥协商协议.在协议中,所有用户共享一个秘密信息,通过较少的步骤,同时实现密钥协商和用户认证.提出的协议满足如下的安全特性:部分密钥泄漏的安全性、完备的前向安全性、个人密钥泄漏的安全性、无不明的密钥共享和无法控制密钥等.

摘要:支持大容量和高并发度的媒体库越来越流行.利用传统的基于纯粹的服务器/客户端、对等网络或网格的方法构造这种类型的媒体库,难以同时满足高并发度和可靠服务的要求.提出了一种结合了网格和对等网络(peer-to-peer)的媒体库架构--NeoMedia.专用的和志愿参与服务的节点在系统服务器的支持下,形成了一个大容量的虚拟媒体存储池,请求服务的节点在从媒体存储池下载媒体文件的同时,在系统服务器的协调下,采用对等网络的方式相互提供服务,从而进一步提升系统的性能.系统服务器还根据虚拟媒体池的负载模式和强度的变化自动调整服务的资源分配,自适应地优化系统的性能.NeoMedia面向的是下载完毕再观看这种可以充分利用服务器的带宽和客户机能力的模式.理论分析表明:系统能够在使用较少的系统带宽的情况下,支持巨大的并发的用户请求,并且提供非平凡服务.

摘要:针对移动支持协议的移动管理代价进行了研究,提出了一种合适的网络模型.在此网络模型的基础上,采用理论分析的方法分析了使用各移动支持协议时,为支持MH(mobile host)移动给网络带来的信令开销,并采用数值仿真的方法,对只使用移动IP协议和引入层次移动时的信令开销以及采用MIP-RR,CIP和HAWAII等不同微移动协议时的信令开销进行了比较.结果表明:引入层次移动与只使用移动IP相比,显著减少了网络的信令开销;在不同的微移动协议中,使用显式删除旧路径的路径维护策略与频繁发送周期性的刷新报文相比,给网络带来的信令开销较小;使用路径更新报文发送到交叉MRA(mobile routing Agent)的路径更新方法与路径更新报文发送到GW(gateway)相比,具有较小的网络信令开销.

摘要:节点可以自由、自主地进入网络拓扑的特性,使得移动Ad hoc网络(mobile ad hoc network,简称MANET)被广泛应用于诸如灾难救援、战场等多种环境中.MANET中的路由要能迅速地适应频繁的网络拓扑结构的变化,同时最大限度地节约网络资源.OLSR(optimized link state routing protocol)协议是一个重要的MANET路由协议,而支撑此协议的一个关键技术是MPR(multipoint relays).在介绍了OLSR协议及MPR技术之后,揭示了目前启发式算法在寻找最小MPR上的弱点,提出了一种基于遗传算法(genetic algorithm,简称GA)的新算法,并证明了该算法的收敛性.通过采用不同遗传策略将此遗传算法衍生成了4个系列算法,并在随机生成的拓扑上对其进行模拟.模拟结果分析显示:提出的遗传算法是可行和适用的,选择的启发式策略也是恰当和正确的.

摘要:文档安全性对于信息共享Peer-to-Peer(或P2P)系统而言是一项重要的性能指标,以P2P系统的文档安全性优化为目标.P2P系统的文档安全性主要取决于两方面的因素:其载体的安全性和文档相关机制的构造,如副本管理等.对于P2P这样高度自主的分布式系统而言,文档安全性的提高无法依赖于结点安全性的提高,而应依靠对文档相关机制的控制来实现.首先设计了一个对文档安全性敏感的查询协议,以该查询协议为基础,与文档相关的机制就可以形式化地表述为函数,而系统文档安全性的提高就转化为函数空间上的数学分析.基于函数分析的结果,设计了一套旨在提高文档真实性的副本管理算法集合.理论分析的结果表明:在理想情况下,该算法集合可达到文档真实性的优化.对于实际系统,经过大量的模拟实验结果验证,该算法集可以获得良好的效果,接近优化水平.

摘要: