• 2007年第18卷第1期文章目次
    全 选
    显示方式: |
    • 一种扩展了价格信息的时间Petri网

      2007, 18(1):1-10.

      摘要 (5053) HTML (0) PDF 767.00 K (4517) 评论 (0) 收藏

      摘要:性能和成本分析是业务流程建模的主要目的,扩展了时间信息的Petri网能够有效地进行性能分析,但是对成本分析却无能为力.提出一种扩展了价格信息的时间Petri网--价格时间Petri网.首先为时间变迁扩展价格参数,并使用价格时间变迁系统给出价格时间Petri网的语义;然后提出计价状态类的概念,并证明为状态类扩展累积成本的合理性和完备性;进而给出一种算法来证明有界价格时间Petri网的最小成本可达问题是可判定的;最后给出一个应用例子并得出结论:为时间Petri网扩展价格信息并将其应用于业务流程管理领域是可行的.

    • 时间约束Petri网及其可调度性分析与验证

      2007, 18(1):11-21.

      摘要 (4480) HTML (0) PDF 902.74 K (4815) 评论 (0) 收藏

      摘要:时间约束Petri网(timing constraint Petri nets,简称TCPN)是一类重要的时间Petri网系统.对相关定义重新界定,丰富并完善了TCPN理论.针对变迁可调度原始定义的不足,首先给出了变迁的弱/强可调度的新定义及强可调度判定定理;然后对变迁的强可调度进行了拓展,提出了TCPN时间可调度的概念,并结合Petri网结构给出了TCPN时间可调度判定定理;最后对TCPN的相关特性进行了研究.TCPN对时间Petri网的研究工作将起到启发作用,并对实时系统的描述和建模工作具有一定的参考价值.

    • Petri网共享PP-型子网合成性质分析

      2007, 18(1):22-32.

      摘要 (3846) HTML (0) PDF 875.27 K (4193) 评论 (0) 收藏

      摘要:Petri网合成可以避免状态空间按指数阶迅速扩大的问题,并且在网扩大时可以保持原网的某些优良性质.为了解决资源共享问题,焦莉等人对于一个满足死锁-陷阱性质(ST-property)的非对称选择网(asymmetric choice,简称AC)进行库所合并,给出了合并后的网保持原网活性、有界性和可回复性的条件.主要动机是对焦莉等人的研究结果进行推广,把对于AC网的库所合并问题推广到AC网或更一般的Petri网上的子网共享合成问题.给出了使共享PP-型子网合成Petri网系统保持活性、有界性和可回复性的条件以及多个AC网进行共享PP-型子网合成,使得到的合成网仍为AC网的条件.结果可为Petri网系统合成的静态和动态性质的考察提供有效途径,为Petri网复杂大系统的分析提供一定的手段.

    • G?del n值命题逻辑中命题的α-真度理论

      2007, 18(1):33-39.

      摘要 (3632) HTML (0) PDF 435.15 K (3836) 评论 (0) 收藏

      摘要:为了在n值命题逻辑系统中建立一种程度化推理机制,并为其提供一个可能的近似推理框架,利用势为n的均匀概率空间的无穷乘积,在n值G?del命题逻辑系统中引入命题的α-真度概念.证明了一般真度推理规则,给出了判定α-重言式的充分必要条件,并利用命题的α-真度定义了命题间的α-相似度,进而导出命题集上的一种伪距离,使得在n值命题逻辑系统中展开近似推理成为可能.提出的程度化推理方法为近似推理的算法实现奠定了基础,并对知识推理的程度化有所启示.

    • 关于二元延迟3步前馈逆有限自动机的结构

      2007, 18(1):40-49.

      摘要 (3688) HTML (0) PDF 1.28 M (3315) 评论 (0) 收藏

      摘要:前馈逆有限自动机的结构是有限自动机可逆性理论中的基本问题.对延迟步数≥3的前馈逆结构的刻划,则是一个长期的未解决问题.研究了二元延迟3步前馈逆有限自动机的结构.对于自治有限自动机Ma的状态图为圈的二元延迟3步弱可逆半输入存储有限自动机C(Maf ),给出了其长3极小输出权分别为1,2,8三种情形下结构的一种刻画.由于C(Maf )延迟3步弱可逆当且仅当它是延迟3步弱逆,因此,得到了二元延迟3步前馈逆有限自动机结构的一种部分刻画.

    • 场景驱动的构件行为抽取

      2007, 18(1):50-61.

      摘要 (5332) HTML (0) PDF 770.53 K (4424) 评论 (0) 收藏

      摘要:如果构件含有冗余的功能,特别是含有用户不想要的功能,则无法被用户正确使用.因此,如何从构件中提取场景规约中所描述的用户想要的行为便是一个亟待解决的问题.给出了解决该问题的一种方法.该方法通过为构件构造一个环境,即极大包含环境,使得场景规约中所描述的所有行为可以从构件中抽取出来,并保留到该构件与其极大包含环境的组合中.同时,构件中的其他行为,即不在场景规约中的行为,被尽可能地舍弃.用接口自动机为构件的行为建模,并将用消息序列图描述的场景规约抽象为一组活动序列.构件的组合描述为接口自动机的乘积.给出了基于场景进行构件行为抽取的相关算法,并用一个实例对文中所述方法进行了说明.

    • 一种基于时间自动机的实时系统测试方法

      2007, 18(1):62-73.

      摘要 (5678) HTML (0) PDF 760.47 K (5917) 评论 (0) 收藏

      摘要:基于时间自动机(timed automata,简称TA)的一种变体--时间安全输入/输出自动机(timed safety input/output automata,简称TSIOA),提出了一种实时系统测试方法.该方法首先将时间安全输入/输出自动机描述的系统模型转换为不含抽象时间延迟迁移的稳定符号状态迁移图(untimed stable transition graph of symbolic state,简称USTGSS);然后采用基于标号迁移系统(labeled transition system,简称LTS)的测试方法来静态生成满足各种结构覆盖标准的包含时间延迟变量迁移动作序列;最后,给出了一个根据迁移动作序列构造和执行测试用例的过程,该过程引入了时间延迟变量目标函数,并采用线性约束求解方法动态求解迁移动作序列中的时间延迟变量.

    • 一种基于异常传播分析的数据流分析方法

      2007, 18(1):74-84.

      摘要 (3942) HTML (0) PDF 671.46 K (4106) 评论 (0) 收藏

      摘要:异常处理是一种用来检测异常并对其进行处理的技术.异常传播改变了程序原来的执行路线,从而改变了程序中的数据流.在进行数据流分析时,如果不考虑异常传播对其造成的影响,则得到的信息将是不准确的.在分析C++异常传播机制和异常传播对数据流分析影响的基础上,提出一种包含异常传播信息的函数间控制流图的构建方法.该控制流图可以清晰地表示出异常的隐式控制流和异常的传播路径;然后提出了基于异常传播分析的数据流分析方法,并给出相应的算法.该方法既克服了因忽略异常传播对数据流影响而造成分析结果不准确的不足,又有助于实现异常传播数据流分析的自动处理;最后用一个实例验证了该方法的可用性.该方法可以为结构测试、回归测试、程序切片等软件工程任务提供相关信息.

    • 基于目标距离评估的启发式Web Services组合算法

      2007, 18(1):85-93.

      摘要 (4344) HTML (0) PDF 529.68 K (4705) 评论 (0) 收藏

      摘要:随着可用Web Services数量的快速增长,如何根据用户的需求来自动组合Web Services,生成满足用户需求的组合业务,成为一项亟待解决的课题.提出了一种基于用户需求目标距离评估的启发式算法,通过该算法,动态调用Web Services来自动生成满足用户所需目标的Web Service组合,同时,该算法还能够根据Web Services组合经验,对以后的Web Services组合方案进行调整.实验结果表明:该算法能够很好地适应网络上Web Services的不稳定情况,与同类算法进行性能比较,也显示出基于目标距离评估的算法具有较好的性能.

    • 一种基于模型的特征交互检测方法

      2007, 18(1):94-104.

      摘要 (3859) HTML (0) PDF 653.07 K (3863) 评论 (0) 收藏

      摘要:为了适应业务的不断更新,许多软件系统通过向公共的基础系统插入新的扩展来实现演化.这种演化策略虽然有利于并行开发和部署,但也面临着扩展间可能发生非预期特征交互的问题.目前,形式化方法在检测特征交互问题方面仍然是最有效的方法之一.这类方法着眼于检测扩展之间是否会发生冲突.虽然在小规模实验上较为成功,但是它们也面临着一些挑战.例如:扩展的非单调性、扩展组合的激增以及扩展模型可能无法获知的问题.实际上,许多特征交互都源于新扩展对基系统和已有扩展造成的不恰当影响.基于这种认识,集中关注由于扩展的不恰当影响所导致的交互冲突问题,提出了如何从已知的特征交互实例来分析产生冲突的原因的具体方法,并说明了如何制定约束以限制扩展中易导致冲突的行为,从而预防同一类行为可能导致的各种冲突.该方法被应用到电信系统特征交互的分析上,实验结果表明,大部分特征交互中导致冲突的行为都可以被检测出来.该方法不仅能够保证原有基系统或扩展模型的稳定、有效,避免扩展组合带来的问题,而且它无须公布扩展的模型细节.

    • 基于轨迹标签的无结构P2P副本一致性维护算法

      2007, 18(1):105-116.

      摘要 (4186) HTML (0) PDF 743.85 K (3757) 评论 (0) 收藏

      摘要:副本的存在是一种提高P2P系统的可扩展性、容错性、可用性和减少查询响应时间的有效手段.随着P2P应用逐渐由只读静态文件共享转换为需要实时更新的读写动态文件交互,副本一致性维护成为确保新业务正确运行的关键.从直接更改消息报文角度出发,提出一种基于节点轨迹标签的无结构P2P副本一致性维护算法,通过在传输消息的报文中添加已接收更新消息的节点轨迹地址链表标签,可以在消息传输源节点进行冗余判断,以减少冗余消息数目.同时,针对直接存储节点地址轨迹标签算法的消息长度随着消息传输轮数和网络度数增加而不断加大的问题,提出一种用Bloom filter替代地址链表轨迹标签的算法.通过Bloom filter这种简洁的结构表示地址链表,可以减少添加到报文中的轨迹长度,利用Bloom filter的"或"运算可以简化传输节点的冗余判断.实验结果表明:节点轨迹标签算法可以极大地降低冗余消息数目,提高P2P系统的可扩展性.副本节点网络连通性越强,消息数目和传输带宽的减少就越明显.该研究可以用到传感器网络等其他自组织网络的一致性维护中.

    • 基于有状态Bloom filter引擎的高速分组检测

      2007, 18(1):117-126.

      摘要 (5245) HTML (0) PDF 629.39 K (4973) 评论 (0) 收藏

      摘要:越来越多的网络安全技术通过分析网络分组中的内容来检测报文中是否含有恶意攻击代码.为了能够在线检测攻击,部署在路由器中的分组检测模块对于分组检测的速度也提出了越来越高的要求.虽然在这个领域已有很多研究工作,然而在性能、可扩展性和适用性方面还有很多可研究的空间.提出了一种基于有状态Bloom filter引擎的高速分组检测方法State-Based Bloom filter engine(SABFE).通过并行查找Bloom filter和前缀寄存器堆,以及利用多个并行的Bloom filter引擎进行流并行检测,达到了较高的吞吐性能.同时,利用快速查找表和前缀寄存器堆保存当前子串的匹配状态来检测长的规则.分析和模拟实验表明:该方法在规则长度增加时依然保持了较高的吞吐性能,可以实现线速的分组检测,同时,极大地减少了硬件资源开销,提高了可扩展性.

    • 无线传感器网络多重覆盖问题分析

      2007, 18(1):127-136.

      摘要 (4710) HTML (0) PDF 788.35 K (4206) 评论 (0) 收藏

      摘要:传感器网络由大量能量有限的微型传感器节点组成.因此,如何保证在足够覆盖监测区域的同时延长网络的寿命,是一个需要解决的重要问题.为了达到这一目标,一种广泛采用的策略是选出部分能够足够覆盖监测区域的节点作为工作节点,同时关闭其他冗余节点.提出了一个数学模型,使得只要已知监测范围和节点感知半径的比值,就可以计算出达到服务质量期望所需要的节点数量.需要指出的是:与大部分研究覆盖的文献不同,该研究不基于节点的位置信息,因此可以极大地降低硬件成本,并且减少节点获得和维护位置信息的开销.模拟实验结果表明:在随机部署条件下,服务质量期望与实验所得到的实际覆盖度的误差不大于服务质量期望的2%;而对于相同的服务质量期望和实际覆盖度,计算所得的工作节点数量与实验所得的工作节点数量的误差小于计算数量的5%,这表明推导出的节点数量与服务质量期望之间的关系与模拟实验的结果相吻合.该结果可以广泛应用于传感器网络的节点部署、拓扑控制等领域中.

    • 用于评估网络信息系统的风险传播模型

      2007, 18(1):137-145.

      摘要 (5456) HTML (0) PDF 904.20 K (5712) 评论 (0) 收藏

      摘要:为了评估网络信息系统的安全风险,提出了一个由风险网络和风险传播算法构成的风险传播模型,并以一个具有代表性的实例阐明了该模型在网络风险评估中的应用,验证了传播算法的正确性.实例分析表明,应用风险传播模型的评估方法较传统方法在评估结论的准确性和制定符合最优成本效应的安全建议等方面更具优势.

    • 内容传递网络处理能力受限代理放置贪婪算法

      2007, 18(1):146-156.

      摘要 (9288) HTML (0) PDF 728.16 K (15066) 评论 (0) 收藏

      摘要:提出了旨在提高内容传递网络服务性能的代理放置策略CCSP(capacity-constrained surrogate placement).CCSP在保证最大化系统吞吐量的条件下,以最小化系统通信开销为目标,求解最优的代理放置方式.与通信网络中的资源分配问题现有求解策略不同,CCSP通过模拟内容传递网络的请求路由机制,考虑了代理服务器的负载分布及处理能力约束,从而保证系统具有最低的资源消耗、最大的吞吐能力和良好的负载均衡.提出了高效的贪婪算法用以求解树型网络条件下的CCSP问题,并通过仿真实验系统地分析了算法的有效性.

    • 基于相似度加权推荐的P2P环境下的信任模型

      2007, 18(1):157-167.

      摘要 (6815) HTML (0) PDF 647.89 K (7926) 评论 (0) 收藏

      摘要:在诸如文件共享等无中心的Peer-to-Peer网络中,对等节点具有匿名性和高度自治的特点,并且由于缺乏对与之交互的节点的可信程度的知识,节点需应对交互过程中可能出现的威胁.提出了一种基于节点评分行为相似度加权推荐的peer-to-peer环境下的全局信任模型(简称SWRTrust),用于量化和评估节点的可信程度,给出了模型的数学表述和分布式实现方法.已有的全局信任模型建立在信任值高的节点其推荐也更可信这个假设基础上,SWRTrust对该假设的合理性提出了质疑.分析及仿真实验结果表明,SWRTrust较已有模型适用于遏制更广泛类型的恶意节点攻击,在迭代的收敛速度和网络中的成功下载率等性能指标上有较大提高.

    • 基于分布式密钥生成方法的RSA可验证签名分享设计

      2007, 18(1):168-176.

      摘要 (4169) HTML (0) PDF 570.47 K (3808) 评论 (0) 收藏

      摘要:主要研究由Franklin和Reiter提出的可验证签名分享(VΣS).它可以允许一个签名的接受者在n个代理之间分享该签名,使得代理者的一些子集以后可以重构该签名.利用安全的分布式密钥生成方式、门限密码系统以及可验证秘密分享,给出了一个RSA VΣS的新协议.该协议是有效的、可证安全的,并且可以容忍至多一半代理的恶意行为.

当期目录


文章目录

过刊浏览

年份

刊期

联系方式
  • 《软件学报 》
  • 主办单位:中国科学院软件研究所
                     中国计算机学会
  • 邮编:100190
  • 电话:010-62562563
  • 电子邮箱:jos@iscas.ac.cn
  • 网址:http://jos.org.cn/
  • 刊号:ISSN 1000-9825
  •           CN 11-2560/TP
  • 国内定价:70元
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号