Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2012年 第49卷 第9期    出版日期:2012-09-15
论文
静态缺陷检测中的误报消除技术研究
赵云山 宫云战 周 傲 王 前 周虹伯
2012, 49(9):  1822-1831. 
摘要 ( 743 )   HTML ( 0)   PDF (1270KB) ( 787 )  
相关文章 | 计量指标
误报率是衡量静态缺陷检测工具的重要指标.在对比分析了各种误报消除技术的基础上,提出了一种前向数据流分析结合逆向约束搜索技术的误报消除方法:前向数据流分析的保守数据流解可以用于缺陷状态迭代,并得到初始的缺陷检测结果;根据缺陷发生处的数据流特征,逆向搜索可能导致缺陷发生的约束条件,该约束条件可以作为通用约束求解器的输入判断缺陷的可满足性,从而对初始的缺陷检测结果进行精化.同时,在数据流分析过程中引入符号执行技术,不仅提高了数据流分析的精度,且便于约束表示及转化,提高了约束搜索的效率.对SPEC CPU2000中11个工程的对比实验表明,前向数据流分析与逆向约束搜索相结合的误报消除方法在增加了有限开销的同时有效地消除了部分误报,且与同类工具相比具有更好的可扩展性.
基于局部堆内存抽象表示的堆操作程序内存泄露检测
董龙明, 王 戟, 陈立前, 董 威,
2012, 49(9):  1832-1842. 
摘要 ( 776 )   HTML ( 1)   PDF (1856KB) ( 643 )  
相关文章 | 计量指标
堆操作程序通过共享易变数据结构可灵活地申请、合并、删除堆内存.这类程序的内存泄漏检测要求精确的域敏感的指针别名信息,变得尤其复杂和难以处理.针对这个问题,提出了基于“指针扩展类型”域敏感的堆内存抽象方法,对指针变量在形态上的排列关系进行抽象以支持堆的局部推理.首先,定义了各种基本语句的操作语义,然后基于该抽象方法采用前向数据流迭代算法提出了一种新的内存泄露检测算法.在Crystal编译框架下实现了面向C程序的内存泄漏检测原型工具Heapcheck,该工具支持复杂数据结构内指针型数据域上的内存泄露检测.在典型基准C程序上的实验结果分析表明,该方法与现有的技术相比在效率和精度上都具有优势.
基于编译支持错误跟踪的测试用例自动化生成方法
何炎祥 陈 勇 吴 伟 徐 超 吴黎兵
2012, 49(9):  1843-1851. 
摘要 ( 579 )   HTML ( 2)   PDF (1293KB) ( 579 )  
相关文章 | 计量指标
测试用例的自动生成是实现测试自动化的重要保障,是验证可信软件的基本方法.在分析现有测试用例自动生成方法的基础上,提出了一种基于编译的错误可跟踪的测试用例自动生成方法.该方法以编译器为依托,通过对其语法和语义进行扩展,将测试需求很好地融入到源程序中参与分析,并利用代码生成器在生成目标代码的同时根据相应的分析结果直接生成对应的测试用例.该方法将测试用例和目标代码生成统一到编译器中,避免了独立的测试用例自动生成工具在获得编译器相关分析结果时而导致的接口开销.同时,通过对源程序行号信息的跟踪,使得测试用例在无法通过测试时能够很快定位出错位置,以方便程序开发者修改.最后,通过一个示例程序说明了该方法的具体实现过程,证明了该方法的有效性.
基于域敏感指向分析的区间运算在软件测试中的应用
周虹伯 金大海 宫云战
2012, 49(9):  1852-1862. 
摘要 ( 514 )   HTML ( 0)   PDF (1145KB) ( 556 )  
相关文章 | 计量指标
静态分析由于并不执行源代码,导致无法获取变量在实际运行中的取值,进而对一些和变量取值相关的缺陷检测带来了一定困难.利用符号执行和区间运算技术,虽然可以模拟程序实际执行时变量的可能取值范围,但对于结构体、数组等,由于不能对其成员进行独立描述,导致数据流无法支持域敏感分析,对和其成员变量相关的缺陷的检测难以实现,产生很多漏报.基于域敏感指向分析的区间运算模型,在域敏感指向分析模型的基础上对其进行了改进,将复杂数据类型拆分成独立的成员变量进行分析,并提出一种关联抽象取值集的类型系统,该系统可以保守的描述程序在动态执行时变量的可能取值.结合赋值语句的抽象语法定义,给出了该类型系统在数据流计算时的具体推导算法,并将其应用在缺陷检测系统(DTSGCC和DTSCPP)中.选用DTSCPP作为实验平台,对6个C++开源工程进行了测试,并对其数据进行了统计分析,结果表明该方法可以减少漏报,且测试效率与非域敏感版本相当.
基于扩展逻辑变换系统μTS证明循环优化正确性
王昌晶
2012, 49(9):  1863-1873. 
摘要 ( 537 )   HTML ( 0)   PDF (1101KB) ( 651 )  
相关文章 | 计量指标
循环优化对于提高Cache性能、发掘程序的并行性以及减少执行循环的开销都有着重要的作用,证明带循环优化功能的现代编译器的正确性已成为可信编译的一个挑战性的问题.形式化证明一个羽翼丰满的优化编译器本质上是不可行的,可以使用替代的方法,即不是证明优化编译器本身,而是形式化证明每一次循环变换前后编译对象的正确性.提出一种新颖的基于扩展逻辑变换系统μTS来证明循环优化正确性的方法.系统μTS在逻辑变换系统TS的基础上扩展了若干条派生规则,经谓词抽象将源程序与目标程序转换为形式化Radl语言后,使用μTS的派生规则能证明常见循环变换的正确性,如循环融合、循环分配、循环交换、循环反转、循环分裂、循环脱皮、循环调整、循环展开、循环铺盖、循环判断外提、循环不变代码外提等.循环优化可以看作一系列循环变换的组合,从而系统μTS能证明循环优化的正确性.为了支持自动化证明循环优化的正确性并出示证据,进一步提出了一个辅助证明算法.最后通过一个典型实例对这一方法进行了详细的阐述,实际效果表明了该方法的有效性.该方法对设计高可信优化编译器具有重要的指导意义.
程序的动态完整性:模型和方法
吴 昊 毋国庆
2012, 49(9):  1874-1882. 
摘要 ( 561 )   HTML ( 2)   PDF (1331KB) ( 505 )  
相关文章 | 计量指标
在信息安全和可信计算中,程序的动态完整性是一个重要问题,特别是无线传感器网络、云计算平台等这一类开放松耦合环境下,怎样度量程序行为的动态完整性的问题尤为突出.基于硬件的可信计算技术和代码证实技术等都没有解决具体行为的动态性度量这个问题,部分原因是缺少一个动态完整性的模型和相应的理论.针对上述问题,在分析了对程序动态完整性安全的威胁基础之上,提出了一个基于密码学的动态完整性理论模型,该模型刻画了程序动态完整性安全的各个要素.基于该模型提出了编译器辅助的流嵌入法,给出了此方法的示例,并分析了此方法的安全性和效率,最后讨论了编译器支持的相关问题,解决了动态完整性的理论和方法中的部分问题.
多子种群微粒群免疫算法及其在函数优化中应用
吴建辉, 章 兢, 李仁发, 刘朝华,
2012, 49(9):  1883-1898. 
摘要 ( 414 )   HTML ( 0)   PDF (2610KB) ( 569 )  
相关文章 | 计量指标
为克服基本微粒群算法的早熟问题,借鉴多子种群和自适应的思想,提出了基于两层模型的多子种群自适应多态杂交微粒群免疫算法.该算法首先通过对若干个子种群进行低层自适应多态杂交微粒群操作,改善了子种群的多样性,有效抑制了收敛过程中的早熟停滞现象;然后通过高层免疫克隆选择操作,显著地提高了全局寻优能力,进一步提高了收敛精度.针对函数优化的仿真结果表明:与其他改进微粒群算法相比,该算法具有更快的收敛速度和更高的求解精度,尤其适合高维及多模态优化问题的求解.
求解平衡约束圆形Packing问题的快速启发式并行蚁群算法
黎自强, 田茁君, 王奕首, 岳本贤,
2012, 49(9):  1899-1909. 
摘要 ( 627 )   HTML ( 1)   PDF (3202KB) ( 529 )  
相关文章 | 计量指标
带平衡约束圆形Packing问题属于NP-hard问题,求解困难.提出一种求解该问题的快速启发式并行蚁群算法.首先提出一种启发式方法:在轮盘赌选择定序的概率公式中增加质量因子和外围逆时针排列定位待布圆,并用它构造出多样性种群个体(相交圆数不超过3的布局方案).然后将蚁群优化与并行搜索相结合,使种群个体快速收敛到最优解或迭代出存在少量干涉的近似最优解(1~3个相交圆).若为后者,则基于物理模型用最速下降法将其快速调整成最优解.所采用的启发式方法、并行蚁群搜索机制和快速调整策略有机结合提高了算法的搜索精度和效率.数值实验表明该算法在性能指标上优于已存在的算法.
RFID数据流上多目标复杂事件检测
彭商濂, 李战怀, 李 强, 陈 群, 刘海龙,
2012, 49(9):  1910-1925. 
摘要 ( 663 )   HTML ( 1)   PDF (5017KB) ( 488 )  
相关文章 | 计量指标
已有的RFID复杂事件处理技术主要关注于单个RFID对象的复杂事件检测和优化技术.实际上,很多RFID应用中往往需要同时检测多个同类型关联目标的复杂事件序列.研究了多个关联的RFID对象的复杂事件处理问题.通过扩展的事件语言和算子的语义以支持同类型多个RFID目标复杂事件查询的定义.通过模式的变换规则,将RFID应用中存在的各种非线性多目标复杂事件模式转换成线性模式,以便各种多目标模式在一个统一的框架下检测.提出了基于自动机NFA\-{b2}的多目标复杂事件检测模型和多目标复杂事件检测算法.通过在多目标检测算法中使用关键节点下压和同位置约束置后优化策略,大大减少了单个类型上无用实例的数目和不同类型间模式匹配的搜索空间.与SASE算法的实验比较表明算法的正确性和高效性.
XML数据流分页频繁子树挖掘研究
雷向欣, 杨智应, 黄少寅, 胡运发,
2012, 49(9):  1926-1936. 
摘要 ( 612 )   HTML ( 0)   PDF (2542KB) ( 870 )  
相关文章 | 计量指标
随着XML数据流的广泛应用,从挖掘XML数据流中发现知识具有重要的理论与应用价值.相比其他频繁模式挖掘,大型XML文档与数据流的频繁子树挖掘面临困难:XML数据流不可能整体在内存解析;对XML数据流分段挖掘必须考虑XML数据的半结构化特征等.针对上述问题,提出数据流分页频繁子树挖掘模型Tmlist.Tmlist对XML数据流进行分页,管理跨页节点及频繁候选子树的跨页增长,逐页挖掘频繁子树;频繁候选子树的增长根据根节点层次由浅至深地在最右路径加入频繁候选节点,避免以低层次为根子树的重复性递归增长;对频繁候选子树采用子树拓扑序列和最右路径共同标识,子树的增长不需要对子树前缀进行匹配,省去前缀节点存储与匹配开销;以页面最小支持度对频繁候选子树按页筛选,子树按页面衰减度衰减支持度、剪枝.Tmlist在可控误差范围内降低频繁子树挖掘的空间消耗,提高内存利用率和挖掘效率.
一种基于LDA的Web论坛低质量回帖检测方法
韩晓晖 马 军 邵海敏 薛 冉
2012, 49(9):  1937-1946. 
摘要 ( 544 )   HTML ( 0)   PDF (2393KB) ( 453 )  
相关文章 | 计量指标
为了过滤Web论坛中的低质量回帖,提出了一种新的基于LDA(latent Dirichlet allocation)的低质量回帖检测方法.不同于以往的方法,该方法在对回帖进行质量分类时使用了两类特征:语义特征和统计特征.提出并定义了垃圾非重要(JI)主题比例、主题不确定度和主题相关度3种语义特征.为克服TF·IDF方法在表示稀疏文本语义上的局限性,语义特征在LDA主题空间上计算.另外,统计特征包括浅层特征、句法特征和论坛专有特征.由于检测回帖质量可被看作二元分类问题,训练SVM分类器来区分出低质量回帖.在3个不同数据集上的实验结果表明,新方法在精确率、查全率和F\-1测度上均优于已知的方法.
两层传感器网络中安全Top-k查询协议
李 睿 林亚平 易叶青 熊 帅 叶松涛
2012, 49(9):  1947-1958. 
摘要 ( 611 )   HTML ( 0)   PDF (2024KB) ( 510 )  
相关文章 | 计量指标
在两层结构传感器网络中,存储节点收集传感器采集的数据,负责处理Sink的查询.在敌对环境中,存储节点可能会被攻击者妥协而泄露传感器所采集的敏感数据以及向Sink返回不完整的或虚假的查询结果.为此,提出了一种安全Top-k查询协议:SecTQ,SecTQ在保证存储节点正确执行查询的同时能有效防止敏感数据的泄露.为了保护数据的隐私性,首先将不同传感器采集的数据之间的直接比较转换成传感器采集的数据与Sink提供的查询比较值进行比较,并提出了一种基于扰动多项式函数的隐私保护方案.该方案利用扰动函数对传感器采集的数据和Sink提供的查询比较值进行编码,保证存储节点在不知道数据和查询比较值真实内容的情况下正确地执行查询处理.为了保护查询结果的完整性,提出了一种称之为水印链的方案,该方案能有效检测查询结果的完整性.
无标签数估计的被动RFID标签防冲突二进制树时隙协议
吴海锋 曾 玉 丰继华
2012, 49(9):  1959-1971. 
摘要 ( 424 )   HTML ( 3)   PDF (2868KB) ( 451 )  
相关文章 | 计量指标
为提高射频识别(radio frequency identification, RFID)标签的吞吐量并减少系统的复杂度,针对被动式RFID 标签识别系统,提出了3种新的标签防冲突协议,分别是动态二进制树时隙协议、自适应二进制树时隙协议和分裂二进制树时隙协议.这3种协议均采用二进制树时隙的算法,即标签先随机选择时隙,如果发生冲突,则冲突的标签立即执行二进制树分解,而其余的标签等待,直到分解结束再识别等待的标签.其最大优点在于无需估计标签,可减少系统的复杂度,同时,又能保持较高的识别标签的吞吐量,而且吞吐量不受标签的变化影响.从仿真结果看,所提出的3种RFID标签防冲突协议的最大识别的吞吐量能达到0.425,高于传统的动态帧时隙Aloha协议、树时隙类Aloha协议,并且当标签在5~1 000时,识别吞吐量未产生大的波动.
基于多维熵值分类的骨干网流量异常检测研究
郑黎明, 邹 鹏, 韩伟红, 李爱平, 贾 焰,
2012, 49(9):  1972-1981. 
摘要 ( 553 )   HTML ( 2)   PDF (2998KB) ( 755 )  
相关文章 | 计量指标
针对高速骨干网上异常检测要求高检测效率和低误报率问题,提出了一个基于多维流量数据熵值分类方法.在多个不同维度上采用熵度量流量数据的分布特征,提出了多维高效熵值计算算法有效减低熵值计算的时间和空间复杂度;在每个时间窗口上把不同维度熵值序列排列成检测向量,采用一类支持向量机对检测向量进行分类;对支持向量机分类判断过程中可能出现误报的情况,提出多窗口关联检测算法,通过在多个连续时间窗口上对异常向量进行多窗口关联检测,最终判断异常是否发生.通过在真实网络流量数据集上的两个对比实验,验证了本文算法在检测效率方面随着网络流量和攻击流量的增加时间和空间开销增长较为平缓,在检测精度方面也取得了令人满意的效果.
基于Shell命令和共生矩阵的用户行为异常检测方法
李 超, 田新广, 肖 喜, 段洣毅,
2012, 49(9):  1982-1990. 
摘要 ( 799 )   HTML ( 6)   PDF (2151KB) ( 716 )  
相关文章 | 计量指标
用户行为异常检测是当前网络安全领域研究的热点内容.提出一种新的基于共生矩阵的用户行为异常检测方法,主要用于Unix或Linux平台上以shell命令为审计数据的入侵检测系统.该方法在训练阶段充分考虑了用户行为复杂多变的特点和审计数据的时序相关属性,依据shell命令的出现频率并利用阶梯式的数据归并方法来确定事件,然后构建模型矩阵来刻画用户的正常行为.在检测阶段,首先为每一个当前事件序列构建一个部分正则化共生矩阵,然后根据矩阵2范数计算这些矩阵与模型矩阵的距离,得到距离流,最后通过平滑滤噪处理距离流来判决用户行为.在Purdue大学实验数据和SEA实验数据上的两组实验结果表明,该方法具有很高的检测性能,其可操作性也优于同类方法.
基于Petri网的IRBAC 2000域间动态转换SMER约束违反检测
刘 猛, 王 轩, 黄荷娇, 赵海楠, 张加佳,
2012, 49(9):  1991-1998. 
摘要 ( 594 )   HTML ( 0)   PDF (1352KB) ( 607 )  
相关文章 | 计量指标
Kapadia等人提出的IRBAC2000模型是在基于角色的访问控制(role-based access control, RBAC)模型基础上,通过角色互联和动态角色转换实现管理域间的互操作.职责分离是RBAC模型3个基本安全原则之一,而IRBAC2000模型没有考虑静态职责分离可能会造成域中静态互斥角色约束违反问题.在相关研究基础上分析了该问题,提出一种新颖的基于Petri网模型的分析方法,该方法相比以前文献中的方法简单、直观.给出了根据IRBAC2000模型构造对应Petri网的算法,基于该图形化模型可直观表示IRBAC2000模型,分析和给出了IRBAC2000违反静态互斥角色(static mutual exclusive roles, SMER)约束的充分必要条件和检测算法,通过一个实例分析验证了其有效性与正确性.为了在进行角色关联和用户角色分配操作时不会违反SMER约束,也基于Petri网分析讨论了执行两种管理操作保证安全的先决条件,为IRBAC 2000模型的安全性提供了安全保证机制.
基于细胞自动机的动态多秘密共享方案
周由胜, 王 锋, 卿斯汉, 杨义先, 钮心忻,
2012, 49(9):  1999-2004. 
摘要 ( 515 )   HTML ( 0)   PDF (735KB) ( 536 )  
相关文章 | 计量指标
针对现有基于细胞自动机多秘密共享方案存在安全性较低和可扩展性较差的问题,提出了一种可验证的动态门限多秘密共享方案.方案中参与者的子秘密可以在多次秘密共享过程中重复使用,减少了秘密分发者的计算负担;在不改变现有参与者子秘密的前提下,可动态加入新参与者和新共享秘密;在秘密分发和重构过程中,能够实现参与者对秘密分发者以及秘密重构者对参与者的验证,及时检测和识别分发者对参与者以及参与者对重构者的欺骗,提高了重构秘密的成功率以及方案的安全性.
电子组织:一种具有自适应能力的可重构仿生硬件结构
徐佳庆, 窦 勇, 吕 启, 冯 雪,
2012, 49(9):  2005-2017. 
摘要 ( 507 )   HTML ( 0)   PDF (5696KB) ( 467 )  
相关文章 | 计量指标
具有自适应能力的仿生硬件是容错领域一个新兴的研究方向.同类细胞替换、成体干细胞分化和异类细胞转化等生物机制是人体血液组织健壮性的重要来源.受这些生物机制的启发,提出了一种名为电子组织的自适应可重构多细胞阵列结构.该结构采用了基于标记与识别的数据处理方式,解除了传统多细胞阵列结构中操作与细胞单元间的严格绑定的数据处理方式,使得电子组织具备了更为灵活的细胞单元替换能力,并在此基础上实现了同类细胞替换、成体干细胞分化和异类细胞转化3种仿生机制.这3种机制使电子组织具备了层次化的自我修复能力;成体干细胞分化和异类细胞转化机制又赋予了电子组织自我进化的能力.在FPGA上实现了原型系统,通过故障注入实验验证了原型系统的自我修复能力和自我进化能力;并通过与电子DNA结构的比较,对电子组织的自适应能力进行了分析与讨论.
可重构指令集处理器的代码优化生成算法研究
张惠臻, 王 超, 李 曦, 周学海,
2012, 49(9):  2018-2026. 
摘要 ( 577 )   HTML ( 0)   PDF (1999KB) ( 541 )  
相关文章 | 计量指标
可重构指令集处理器能够适应多变的计算任务在性能和灵活性两方面的要求,而传统的编译后端技术无法为其生成高效的可执行代码,需要有新的代码生成方法.针对传统编译后端代码生成三阶段方法进行扩展的代码混合优化生成算法正是这样一种方法.该算法很大程度地复用了原有的三阶段代码生成过程,同时针对可重构指令集具有动态性的特点,根据系统硬件资源和重构配置,扩展了针对可重构指令代码生成的优化处理,从而能够获得切合可重构指令集处理器体系结构特性的可执行代码.相关实验与分析说明了该算法针对硬件重构得到的新平台所做的可重构指令代码生成是有效的,能够较好地提高应用程序在新平台上的执行性能.
基于同步EDA工具的异步电路设计流程
王友瑞 石 伟 王志英 陆洪毅 苏 博
2012, 49(9):  2027-2035. 
摘要 ( 554 )   HTML ( 0)   PDF (2930KB) ( 494 )  
相关文章 | 计量指标
随着VLSI技术的迅猛发展与应用需求的不断提高,微处理器中的功耗、时钟偏移等问题越来越严重,异步电路及其设计方法受到广泛关注.异步电路设计缺乏通用商业EDA工具的支持,现有的基于同步EDA工具的异步电路设计方法存在复杂度高等问题.提出了一种新的异步电路设计流程.该流程充分利用现有同步EDA工具,通过采用多路虚拟时钟综合方法对电路进行逻辑综合,以及在后端实现时对异步控制通路进行定量延迟分析和精确延迟匹配,可以得到更加优化的电路.使用该流程在UMC 0.18μm工艺下实现了一款异步微处理器内核,实验结果表明该流程能快速有效地进行大规模异步集成电路的设计实现.
使用批量处理方法提高iSCSI存储系统性能的策略研究
韩 永 姚念民 刁 莹
2012, 49(9):  2036-2043. 
摘要 ( 495 )   HTML ( 0)   PDF (1736KB) ( 495 )  
相关文章 | 计量指标
iSCSI存储系统在IP网络上传输SCSI协议,但是在网络上大量的SCSI命令、状态以及小数据的传输严重影响了网络存储系统的性能.传统的批量处理方法将多个小的命令请求合并为一个大的请求,然而参数K的设定基于经验,缺少定量分析.通过排队理论建立SCSI命令批量处理的数学模型,然后在iSCSI存储协议结构中设计K-batch模块,最后应用网络仿真软件ns-2建立仿真场景对存储系统进行测试.随着命令到达率λ的变化,批量处理参数K作相应的实时调整.实验结果显示,该批量处理策略可明显降低命令的平均响应时间,提高iSCSI存储系统性能.