• 2017年第28卷第7期文章目次
    全 选
    显示方式: |
    • Goguen命题逻辑系统公理化扩张的Γ-k真度理论及性质

      2017, 28(7):1629-1639. DOI: 10.13328/j.cnki.jos.005110

      摘要 (2323) HTML (1341) PDF 1.13 M (3329) 评论 (0) 收藏

      摘要:首先对n值Goguen命题逻辑进行公理化扩张,Goguen~,Δ,记为∏~,Δ.利用公式的诱导函数给出公式在kk任取~或Δ)连接词下相对于局部有限理论Γ的Γ-k真度的定义;讨论了∏~,Δ中Γ-k真度的MP规则、HS规则等相关性质;最后,在Γ-k中定义了两公式间的Γ-k相似度与Γ-k伪距离,得到了公式在k连接词下相对于局部有限理论Γ-k的相似度与Γ-k伪距离所具有的一些良好性质.

    • 单规格一刀切矩形排样问题的启发式搜索算法

      2017, 28(7):1640-1654. DOI: 10.13328/j.cnki.jos.005100

      摘要 (2838) HTML (1340) PDF 1.32 M (4802) 评论 (0) 收藏

      摘要:针对单规格一刀切二维矩形排样问题,提出了一种启发式搜索算法,称为大小工件分治择优匹配(bigitemsmallitem divide-and-conquer best-fit,简称BSDBF)启发式算法.该算法基于组化规则,提出了大小工件分治策略和组块快速举荐算法,是对组化策略的关键补充,这对优解获得至关重要.然后,择优选择适应度高的组块进行递归排样,贪心获得各块板材的排样方案.最后,基于设计的工件拆分方法,对初始解进行后处理小规模重排,进一步提升解的质量.因为没有随机因素,其获得的优解可复现,也是BSDBF算法区别于其他算法的典型特征.大量Benchmark案例的实验结果表明,BSDBF算法求解质量优于其他算法的报道结果.

    • ParaC:面向GPU平台的图像处理领域的编程框架

      2017, 28(7):1655-1675. DOI: 10.13328/j.cnki.jos.005241

      摘要 (3442) HTML (1623) PDF 2.08 M (5006) 评论 (0) 收藏

      摘要:GPGPU加速器是当前提高图像处理算法性能的主流加速平台,但在GPGPU平台上,同一个程序充分利用硬件体系结构特征和软件特征的优化版本与简单实现版本在性能上会有数量级的差异.GPGPU加速器具有多维多层的大量执行线程和层次化存储体系结构,后者的不同层次具有不同的容量、带宽、延迟和访问权限.同时,图像处理应用程序具有复杂的计算操作、边界处理规则和数据访问特性.因此,任务的并发执行模式、线程的组织方式和并发任务到设备的映射不仅影响到程序的并发度、调度、通信和同步等特性,而且也会影响到访存的带宽、延迟等.因此,GPGPU平台上的程序优化是一个困难、复杂且效率较低的过程.提出基于语言扩展的领域编程模型:ParaC.ParaC编程环境利用高层语言扩展描述的程序语义信息,自动分析获取应用程序的操作信息、并发任务间的数据重用信息和访存信息等程序特征,同时结合硬件平台特征,利用基于领域先验知识驱动的编译优化模型自动生成GPGPU平台上的优化代码,最后,利用源源变换编译器生成标准OpenCL程序.在测试用例上的实验结果表明,ParaC在GPGPU平台上自动生成的优化版本相对于手工优化版本的加速比最高达到3.22倍,但代码行数只是后者的1.2%~39.68%.

    • 基于验证的自适应系统决策:一种模型驱动的方法

      2017, 28(7):1676-1697. DOI: 10.13328/j.cnki.jos.005257

      摘要 (2724) HTML (2000) PDF 2.42 M (4623) 评论 (0) 收藏

      摘要:自适应系统需要根据运行时上下文和自身的变化进行其行为的调节.为实现自主调节,自适应系统必须被赋予运行时监测上下文和自身变化、分析需求满足程度的变化以及推理得到自适应决策的能力.这种在线决策的行为在满足功能需求的同时,还需要保证系统满足特定的非功能需求,如可靠性和性能等.提出了一种基于验证的自适应系统优化决策方法,以保证非功能需求的满足.该方法在识别可调节目标以建模自适应机制的同时,将系统的目标模型映射为相应的行为模型,用标签转移系统表示;以可靠性需求为例,用标记目标模型规约任务的可靠性;然后将系统行为模型和可靠性规约整合为带可变状态的离散时间马尔可夫链,将候选自适应配置描述为不同可变状态间的组合;最终通过相关需求的在线验证,使系统找到关于某类上下文的最优决策配置.通过一个移动信息系统的案例展示了该方法的可行性和有效性.

    • 面向同步规范的并行代码自动生成

      2017, 28(7):1698-1712. DOI: 10.13328/j.cnki.jos.005056

      摘要 (4514) HTML (1114) PDF 1.39 M (6272) 评论 (0) 收藏

      摘要:随着对安全攸关实时系统功能与非功能要求的日益增加,使用多核技术将成为发展趋势.如何在多核平台条件下保证系统运行的可信任性及可靠性是学术上和应用上的关键问题.目前基于形式化方法的系统设计、验证以及自动代码生成已在单核平台上形成很多研究成果,但在多核平台上的研究仍面临许多科学问题.同步语言SIGNAL是一种被广泛应用于安全攸关实时系统功能设计的形式化方法,适用于对系统确定性并发行为的描述.SIGNAL编译器也支持将同步规范(synchronous specification)生成仿真代码,以对其进行验证与分析.然而,现有研究较少关注从SIGNAL同步规范到支持跨平台并行代码的生成方法.研究了面向SIGNAL同步规范的并行自动代码生成方法.提出了方程依赖图EDG的概念,将SIGNAL规范转换为EDG以分析其全局数据依赖关系;研究了对EDG进行任务划分获取规范中可以并行执行部分的算法;最后,以跨平台并行编程API-OpenMP作为对象,结合程序中信号的时钟关系,将并行任务映射到OpenMP并行代码,并进行了实例验证.

    • 基于证据的软件过程可信度模型及评估方法

      2017, 28(7):1713-1731. DOI: 10.13328/j.cnki.jos.005102

      摘要 (3487) HTML (1597) PDF 1.82 M (4873) 评论 (0) 收藏

      摘要:软件可信已经是一个迫在眉睫的重要问题,但对软件可信性的评估却一直没有一个系统且客观的标准.一些研究工作从可信证据的采集渠道入手,譬如认为有第3方测试的证据,其可信级别就高一些,而若有用户的使用反馈则可信级别就更高.这些工作在可信的客观性方面做了很好的贡献.但可信其实是一个系统性的问题,而且质量形成于过程,其证据的充分必要程度以及对必要开发过程的覆盖程度等非常关键.基于软件开发过程,从过程的实体、行为以及制品3个方面提取软件可信的证据,建立了由37个可信原则、182个过程可信证据和108个制品可信程度证据组成的软件过程可信度模型,并给出基于该模型证据的软件过程可信评估方法,试图从开发过程的可信程度来建立软件产品的可信的信心.

    • 面向Linux的内核级代码复用攻击检测技术

      2017, 28(7):1732-1745. DOI: 10.13328/j.cnki.jos.005058

      摘要 (3507) HTML (1885) PDF 1.49 M (4452) 评论 (0) 收藏

      摘要:近年来,代码复用攻击与防御成为安全领域研究的热点.内核级代码复用攻击使用内核自身代码绕过传统的防御机制.现有的代码复用攻击检测与防御方法多面向应用层代码复用攻击,忽略了内核级代码复用攻击.为有效检测内核级代码复用攻击,提出了一种基于细粒度控制流完整性(CFI)的检测方法.首先根据代码复用攻击原理和正常程序控制流构建CFI约束规则,然后提出了基于状态机和CFI约束规则的检测模型.在此基础上,基于编译器,辅助实现CFI标签指令插桩,并在Hypervisor中实现CFI约束规则验证,提高了检测方法的安全性.实验结果表明,该方法能够有效检测内核级代码复用攻击,并且性能开销不超过60%.

    • 软件可靠性增长模型的不确定性量化研究

      2017, 28(7):1746-1758. DOI: 10.13328/j.cnki.jos.005108

      摘要 (2723) HTML (1357) PDF 410.61 K (3638) 评论 (0) 收藏

      摘要:数量激增的软件系统被开发出来为用户提供了极大的便利,但也给系统开发带来了极大的不确定性.故障调试过程中的故障检测率(fault detection rate,简称FDR)是不规律变化的,且通常被描述为白色噪音.白色噪音具有马尔可夫性,但在实践中,噪音出现非马尔可夫性是普通现象,而噪音呈现马尔可夫性仅仅是例外.在许多真实情况下,白色噪声的理想化假设是不足的:真正的不规则因素总是非马尔可夫相关性的.提出了一个新的模型来量化调试过程相关的环境不确定性因素.基于广泛应用于软件故障检测过程的非齐次泊松过程(non-homogeneous Poissonprocess,简称NHPP)模型,将环境的不确定性考虑为任意分布和时间相关性的噪声.通过与一些现有模型的比较,新的框架表现出更接近实际观测数据的特征.除了常用的关注故障数的平均值以外,还提供了公式以计算其累积密度函数(CDF)和概率密度函数(PDF),从而获得调试过程的完整统计信息.

    • 贪婪缺省逻辑

      2017, 28(7):1759-1772. DOI: 10.13328/j.cnki.jos.005066

      摘要 (3014) HTML (1112) PDF 1.37 M (3713) 评论 (0) 收藏

      摘要:提出了一种贪婪缺省逻辑,旨在构造扩展的过程中尽可能地保留缺省规则当中的信息.给出了贪婪缺省逻辑的推演系统——GD系统和贪婪缺省的GD-扩展的定义.并且证明了对于缺省理论(T,Δ)的一个扩展,必定存在一个贪婪缺省理论的GD-扩展,使得缺省逻辑的扩展是贪婪缺省逻辑扩展的子集.同时,还存在贪婪缺省理论(T,Δ)的某一GD-扩展,该GD-扩展不包含缺省理论的任一扩展.因此缺省逻辑和贪婪缺省逻辑是两种不同的逻辑.

    • 基于进化聚类的动态网络社团发现

      2017, 28(7):1773-1789. DOI: 10.13328/j.cnki.jos.005114

      摘要 (2842) HTML (1430) PDF 1.72 M (4693) 评论 (0) 收藏

      摘要:社团的数目和时间平滑性的平衡因子一直是基于进化聚类的动态网络社团发现算法的最大的问题.提出一种基于标签的多目标优化的动态网络社团发现算法(LDMGA).借鉴多目标遗传算法思想,将进化聚类思想转换为多目标遗传算法优化问题,在保证当前时刻的聚类质量的同时,又能使当前聚类结果与前一时刻网络结构保持一致.该算法在初始化过程中加入标签传播算法,提高了初始个体的聚类质量.提出基于标签的变异算法,增强了算法的聚类效果和算法的收敛速度.同时,多目标遗传算法和标签算法的结合使算法可扩展性更强,运行时间随着节点或者边数目的增加呈线性增长.将该算法与目前的优秀算法在仿真数据集和真实数据集上进行对比实验,结果表明,该算法既有良好的聚类效果,又有良好的扩展性.

    • 高效节能虚拟网络映射多反馈控制模型及算法

      2017, 28(7):1790-1814. DOI: 10.13328/j.cnki.jos.005062

      摘要 (3302) HTML (1601) PDF 2.66 M (3812) 评论 (0) 收藏

      摘要:网络虚拟化使得智能能耗感知网络部署成为可能.由于虚拟网络请求到来以及退出等动态性,引起底层网络资源分配以及回收,会对底层网络激活资源数量与集合范围产生影响;虚拟网络映射不仅决定了当前激活的底层网络资源数量与集合大小,而且作用于后续的虚拟网络映射.利用自动控制原理的反馈控制理论,研究不同虚拟网络映射之间的关系以及当前虚拟网络映射对激活底层网络资源集合产生的影响,并提出一种新的高效节能虚拟网络映射多反馈控制模型及算法.以控制底层网络休眠链路数量作为主反馈,消除主动休眠的底层网络链路数量与被动休眠的链路数量的偏差,抑制虚拟网络映射动态特征对求解最小底层网络激活资源集合的干扰;并以节点和链路映射为局部反馈,由大到小逐步调整主动休眠底层链路数量,快速地找到适合当前虚拟网络请求的最小底层网络资源集合.多反馈控制模型能够把虚拟网络映射在一个较小的节点和链路集合中,从而提高休眠节点和链路数量,实现高效节能虚拟网络映射.系统仿真结果验证了在非饱和状态下虚拟网络映射多反馈控制算法能够提高底层节点和链路休眠数量,显著减少系统能耗;且在负载周期性动态变化的饱和状态下,提高了虚拟网络接收率以及系统收益.

    • 一种大规模IP网络多链路拥塞推理算法

      2017, 28(7):1815-1834. DOI: 10.13328/j.cnki.jos.005111

      摘要 (2727) HTML (1833) PDF 2.04 M (4240) 评论 (0) 收藏

      摘要:基于最小集覆盖理论的拥塞链路推理算法,仅对共享瓶颈链路进行推理,当拥塞路径存在多条链路拥塞时,算法的推理性能急剧下降.针对该问题,提出一种基于贝叶斯最大后验(Bayesian maximum a-posterior,简称BMAP)改进的拉格朗日松弛次梯度推理算法(Lagrange relaxation sub-gradient algorithm based on BMAP,简称LRSBMAP).针对推理算法中链路覆盖范围对算法推理性能的影响,以及探针部署及额外E2E路径探测发包的开销问题,提出设置度阈值(degree threshold value,简称DTV)参数预选待测IP网络收发包路由器节点,通过引入优选系数ρ,在保证链路覆盖范围的基础上,兼顾开销问题,确保算法的推理性能.针对大规模IP网络多链路拥塞场景下,链路先验概率求解方程组系数矩阵的稀疏性,提出一种对称逐次超松弛(symmetry successive over-relaxation,简称SSOR)分裂预处理共轭梯度法(preconditioned conjugate gradient method based on SSOR,简称PCG_SSOR)求解链路先验概率近似唯一解的方法,防止算法求解失败.实验验证了所提算法的准确性及鲁棒性.

    • 基于半色调技术的印前图像篡改检测方法

      2017, 28(7):1835-1846. DOI: 10.13328/j.cnki.jos.005067

      摘要 (3081) HTML (1185) PDF 1.23 M (4269) 评论 (0) 收藏

      摘要:印前图像特指图像数字排版经编辑确认后的数字印刷样张,其以栅格处理器分色后的加网二进制形式存储.数字样张一经确认,其来源的合法性便不受怀疑.但是,从印刷的整体流程来看,数字样张的存储、传输过程中仍有较大的篡改风险.现有的复制移动篡改检测算法存在特征维度高、计算开销大或检测率较低等问题,而且不适用于分色后的二进制样张.提出了一种基于半色调图像网点密度特征的Copy-Move篡改检测方法,该方法对分色处理后的CMYK目标图像进行半色调二值量化处理,采用滑动分块的方法对目标图像进行分块,通过提取图像块CMYK这4个通道的局部网点密度特征对图像块进行篡改检测.实验结果表明,该方法在图像篡改检测上与以往方法相比具有较低的时间复杂度和较高的检测率,并且对图像篡改区域的旋转攻击、小尺度缩放攻击等具有较好的鲁棒性.

    • 三角形约束下的词袋模型图像分类方法

      2017, 28(7):1847-1861. DOI: 10.13328/j.cnki.jos.005069

      摘要 (3416) HTML (1419) PDF 1.48 M (5546) 评论 (0) 收藏

      摘要:视觉词袋模型广泛地应用于图像分类与图像检索等领域.在传统词袋模型中,视觉单词统计方法忽略了视觉词之间的空间信息以及分类对象形状信息,导致图像特征表示区分能力不足.提出了一种改进的视觉词袋方法,结合显著区域提取和视觉单词拓扑结构,不仅能够产生更具代表性的视觉单词,而且能够在一定程度上避免复杂背景信息和位置变化带来的干扰.首先,通过对训练图像进行显著区域提取,在得到的显著区域上构建视觉词袋模型.其次,为了更精确地描述图像的特征,抵抗多变的位置和背景信息的影响,该方法采用视觉单词拓扑结构策略和三角剖分方法,融入全局信息和局部信息.通过仿真实验,并与传统的词袋模型及其他模型进行比较,结果表明,该方法获得了更高的分类准确率.

    • 基于数据均衡的增进式深度自动图像标注

      2017, 28(7):1862-1880. DOI: 10.13328/j.cnki.jos.005112

      摘要 (2726) HTML (1163) PDF 1.96 M (4506) 评论 (0) 收藏

      摘要:自动图像标注是一个包含众多标签、多样特征的富有挑战性的研究问题,是新一代图像检索与图像理解的关键步骤.针对传统的基于浅层机器学习标注算法标注效率低下、难以处理复杂分类任务的问题,提出了基于栈式自动编码器(stacked auto-encoder,简称SAE)的自动图像标注算法,提升了标注效率和标注效果.主要针对图像标注数据不平衡问题,提出两种解决思路:对于标注模型,提出一种增强训练中低频标签的平衡栈式自动编码器(B-SAE),较好地改善了中低频标签的标注效果.并在该模型的基础上提出一种分组强化训练B-SAE子模型的鲁棒平衡栈式自动编码器算法(RB-SAE),提升了标注的稳定性,从而保证模型本身具有较强的处理不平衡数据的能力;对于标注过程,以未知图像作为出发点,首先构造未知图像的局部均衡数据集,并判定该图像的高低频属性以决定不同的标注过程,局部语义传播算法(SP)标注中低频图像,RB-SAE算法标注高频图像,形成属性判别的标注框架(ADA),保证了标注过程具有较强的应对不平衡数据的能力,从而提升整体图像标注效果.通过在3个公共数据集上进行实验验证,结果表明,该方法在许多指标上相比以往方法均有较大提高.

    • 基于运行时模型的混合云管理方法

      2017, 28(7):1881-1897. DOI: 10.13328/j.cnki.jos.005113

      摘要 (2771) HTML (1452) PDF 1.77 M (3706) 评论 (0) 收藏

      摘要:随着云计算技术的普及,涌现出众多不同用途、不同类型的云计算平台.为了满足遗产系统整合和动态资源扩展等需求,常常需要构造混合云来统一管理不同云平台中的计算和存储资源.然而,不同云平台的管理接口和管理机制存在差异,使得开发混合云管理系统难度大、复杂度高.提出一种基于运行时模型的混合云管理方法:首先,在云平台管理接口的基础上,构造单一云平台的运行时模型;其次,根据云平台领域知识,提出一种云平台软件体系结构的统一模型;最后,通过模型转换,实现云平台统一模型到运行时模型的映射.于是,管理程序可以建立在云平台统一模型的基础上,降低了混合云管理系统开发的难度和复杂度.另外,还实现了基于运行时模型的CloudStack和亚马逊EC2混合云管理系统,并对方法的可行性和有效性进行了验证.

    • 基于信任度的合一系统社会任务分配

      2017, 28(7):1898-1925. DOI: 10.13328/j.cnki.jos.005109

      摘要 (2448) HTML (1130) PDF 2.83 M (5678) 评论 (0) 收藏

      摘要:在多智体社会网络中,传统的任务分配模型一般采用直接面向任务执行者的分配机制.它们不考虑社会网络组织结构对任务分配性能的巨大影响,也很少透彻地研究不可靠社会中的任务分配.针对这些问题,开创性地研究了软/硬件合一系统的任务分配,即按递阶、分层的思想设计了协作组织模型,并基于此提出了面向社区基于社会协调"软件人"的任务分配模型.模型研究过程中,提出了基于直接信任度和社区声誉的社区信任度评估机制、基于社区信任度和社区物理能力的节点选择机制、基于负载均衡的社区内任务分配机制和基于上下文资源的任务再分配策略.实验结果表明:与常见的直接面向任务执行者和基于资源的任务分配模型相比,所提出的模型具有更优的任务分配性能,且对社会任务环境变化具有更好的鲁棒性;社区内基于负载均衡的分配机制和基于上下文资源的再分配策略也有效提高了分配性能,降低了网络中的通信密度.

当期目录


文章目录

过刊浏览

年份

刊期

联系方式
  • 《软件学报 》
  • 主办单位:中国科学院软件研究所
                     中国计算机学会
  • 邮编:100190
  • 电话:010-62562563
  • 电子邮箱:jos@iscas.ac.cn
  • 网址:https://www.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号