摘要:布尔可满足性问题（SAT）是指对于给定的布尔公式，是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题，一般认为不存在多项式时间算法，除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT），从全局搜索到局部搜索，给出了大量的相对有效算法，包括随机算法和确定算法.目前，最好算法的时间复杂度不超过O（（2-2/k）ⁿ），当k=3时，最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题，很少有文献涉及.引入了一类可分离SAT问题，即3-正则可分离可满足性问题（3-RSSAT），证明了3-RSSAT是NP完全问题，给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后，利用矩阵相乘算法的研究成果，给出了3-RSSAT问题的O（1.890ⁿ）精确算法，该算法与子句长度无关.

摘要:基于数论转换的Schönhage-Strassen算法（简称SSA）是目前实际应用中使用较多、速度较快的大整数乘法算法之一.首先对SSA算法原理进行了详细分析，然后从细粒度的角度对SSA算法在多核平台进行比较细致的并行优化.基于大整数运算开源库GMP实现了SSA算法并行化方案，并在Intel X86平台进行了验证和测试.经测试，8线程时的最大加速比可达到6.59，平均加速比6.41.在浪潮TS850服务器对并行方案的扩展性进行测试，实验结果表明：SSA算法并行方案具有良好的扩展性，最大加速比可达21.42.

摘要:针对组合服务容错逻辑与执行逻辑不分离，以及容错过程易出现SLA（service level agreement）违反的现状，提出一种SLA感知的事务型组合服务容错方法.该方法首先采用有限状态机建模组合服务执行过程，对其状态进行监控；其次，采用监控自动机监控执行过程中的SLA属性，确保不出现SLA违反；然后，对于补偿过程，采用改进的差分进化算法快速寻找最优恢复规划；最后，该方法与组合服务执行逻辑相分离，所以易于开发、维护和更新.基于真实数据集的实验结果验证了所提方法在故障处理时间与组合最优度方面优于其他方法，并且对不同故障规模适应良好.

摘要:以安全重构元为基础，能够提供高灵活性、适应性和可扩展性安全服务的可重构安全计算系统已成为当前安全研究领域的热点问题.目前，关于重构机理的研究主要采取基于功能候选集的静态重构配置生成方法，可重构安全系统作为一种主动安全防御手段，应具有动态自动重构的能力，避免人工介入导致的脆弱性.针对动态自动可重构安全系统的建模以及配置生成过程的描述问题，提出了一种基于直觉主义逻辑扩展的动态自动可重构安全系统逻辑模型SSPE，给出了逻辑模型SSPE上的语法和推理规则，设计了基于SSPE的等级化安全重构元和安全需求建模和表达方法，并给出了基于映射关系的安全重构元描述向逻辑语言的转换规则.最后，以IPSec协议为例，阐述了可重构安全系统重构配置的动态自动推理生成过程.基于直觉主义逻辑的可重构安全系统建模和配置生成方法，为研究可重构安全系统的重构机理提供了新的思路和方法，具有重要的意义.

摘要:众测是一种新兴的软件测试方法，它依靠网络上的工作者帮助完成测试任务.对于某个测试任务来说，谁来执行对于发现缺陷以及覆盖测试需求关键点是至关重要的.然而众测平台上一般有大量的候选工作者，他们拥有不同的测试经验，也常常提交重复的测试报告.由于众测工作者随机地参与测试任务，同时满足较高缺陷检测率和较高测试需求关键点覆盖度是很困难的.因此，该文关注如何为新的测试任务选择一组合适的众测工作者，从而提高缺陷检测率和需求关键点覆盖度.首先设计了3个实验，试图发现选择什么样的众测工作者能够提升缺陷检测率和需求关键点覆盖度.通过实验验证，发现众测工作者的主动性、相关性和多样性从不同的角度影响测试质量，并且给出了它们的度量方法.然后，提出一种同时考虑这3个方面工作的选择方法.基于众测平台之一——百度众测上46个真实的测试任务对该方法进行了验证，结果显示，该方法能够显著提高缺陷检测率和测试需求关键点覆盖度.

摘要:组合测试可以有效检测待测系统中由参数间交互作用而引发的故障.在其30多年的发展过程中，覆盖表生成一直是关键问题之一，相关研究文献已达200多篇.作为一种有效的覆盖表生成算法，已有的禁忌搜索算法在所生成的覆盖表规模上具备一定的优势，但其解的质量和运算速度仍有提升空间；同时，这些算法实际应用能力较差，既不支持约束处理，也无法生成可变力度覆盖表.针对以上问题，提出了一种禁忌搜索算法.该算法从3个方面对已有的算法进行了改进：1）算法参数配置调优分pair-wise和爬山两阶段进行，确保使用较少配置条数最大程度击中最优配置，进一步提高算法生成覆盖表的规模；2）进行算法并行化，加速算法生成覆盖表的速度；3）增加约束处理和变力度处理，使算法可适应多种测试场景.实验结果表明，该算法在固定力度、变力度、带约束等多种类型覆盖表的规模上都具有一定优势，同时，并行化使算法平均加速2.6倍左右.

摘要:为了适应普适计算环境中用户、设备、使用环境和开发平台的多样性，基于模型的方法被应用于用户界面开发过程中，试图在抽象层次上描述界面，通过模型转换，使其适用于不同的平台.然而，由于目前基于模型的用户界面开发方法（model-based user interface development，简称MBUID）中所采用任务模型的局限性，致使生成的界面难以满足动态环境下用户的可用性需求.提出一种基于任务模型的用户界面开发框架，旨在建模和生成有效、高效、令用户满意的用户界面.在可用性方面，为了准确描述普适计算环境中用户任务，提出一种基于感知控制理论的任务分析方法（perceptual-control-theory-based task analysis，简称PCTBTA），将使用上下文信息引入到任务分析过程中，并且在较高的抽象层次上反映交互的内容，给可用性设计提供任务空间；在技术方面，为PCTBTA任务模型向界面模型的转换提供技术支持.最后，通过实例说明所提出方法的可行性，并通过与其他方法在可用性和性能方面的比较，表明该方法的有效性.

摘要:服务质量（quality of service，简称QoS）是衡量Web服务好坏的重要标准，也是用户选择Web服务的重要依据.能够实时而准确有效地对Web服务进行监控，是Web服务质量保障的重要基础.为此，提出了一种时效感知的动态Web服务QoS监控方法.该方法在传统加权监控方法中融入了滑动窗口机制和信息增益原理，简称IgS-wBSRM（information gain and sliding window based weighted naive Bayes QoS runtime monitoring）.该方法以一定的初始训练样本进行环境因素权值初始化，利用信息熵（information entropy，简称IE）及信息增益（information gain，简称IG）对样本所处混沌状态的确定作用，依次读取样本数据流，计算样本数据单元出现前后各影响因子组合的信息增益，结合TF-IDF（term frequency-inverse document frequency）算法对早期的初始化权值进行动态更新，修正传统算法对监控分类的类间分布偏差问题和参数未更新问题.另外，考虑训练样本数据的时效性，结合滑动窗口机制来对影响因子组合权值进行同步更新，以消解长期累积的历史累赘数据对近期服务QoS的影响.在模拟数据集和开源数据集上的结果表明：利用滑动窗口机制可以有效摒弃历史数据的过期信息，结合滑动窗口机制实现的基于信息增益的动态权值算法能够更加准确地监控Web服务QoS，总体监控效果明显优先于现有方法.

摘要:极小碰集问题是人工智能中的重要问题，应用广泛.碰集极小性判定，作为极小碰集求解过程中的关键步骤，效率的高低会对极小碰集求解算法的耗时产生直接影响.现有的极小碰集求解算法主要使用子集检测方法进行碰集极小性判定.针对子集检测方法在极小碰集簇规模较大时效率较低的问题，提出了基于元素独立覆盖度检测的碰集极小性判定方法——ICC方法，剥离了碰集极小性判定耗时与极小碰集簇大小的相关性；通过深入分析增量求解过程中非极小碰集的产生原因，给出了ICC方法的增量判定形式ⅡCC方法，使其可以尽早发现并丢弃非极小候选解，为使用其增量极小碰集求解算法带来额外的剪枝效果，进一步提升算法的效率.实验结果表明：该方法易于实现，可扩展性强，对于当前效率较高的Boolean算法，使用ⅡCC方法后，算法可求解问题的规模和整体效率均有明显提升，效率提升最高达4个数量级以上.

摘要:互联网的蓬勃发展，在为用户提供便利的同时，其海量信息也为用户选择造成了困难，基于用户理解的信息推荐服务正成为应时之需.相较于面向单个用户信息的传统推荐技术，基于社交信息的推荐技术通过引入影响力建模，可以更真实地还原用户属性及行为.然而，已有的社交推荐技术往往停留于对用户影响的笼统归纳，并没有对其内在机制进行清晰分类和量化.针对这一问题，通过对用户评分行为中的信任关系进行分析，着重研究了信任用户间接影响用户偏好和直接影响用户评分两种不同机制，进而提出了基于用户间信任关系融合建模的概率矩阵分解模型TPMF，从而实现对上述两种机制的有效融合.在此基础之上，针对不同用户受两种机制影响权重不同的问题，通过借助评分相关性对用户进行聚类并映射到相应权重，实现了用户模型参数的个性化选择.公开数据集的多项实验结果表明：提出的TPMF及其衍生算法在各项指标上优于现有代表性算法，验证了所提出的影响机制及技术框架的有效性.

摘要:建立邻接图上的批量边删除聚类算法通用框架，提出基于高斯平滑模型的批量边删除判定准则，定义了适于聚类的邻接图的一般性质，提出并证明在kNN图基础上引入随机因子构造的随机kNN图，可以增强顶点之间的局部连通性，使聚类结果不再强烈依赖于某条边或某些边的保留或删除.RkNNClus算法简洁高效，依赖参数少，无需指定类簇数目，模拟和真实数据上的实验均有证明.

摘要:在基于图像集的流形降维问题中，许多算法的核心思想都是把一个高维的流形直接降到一个维数相对较低、同时具有的判别信息更加充分的流形上.投影度量学习（projection metric learning，简称PML）是一种Grassmann流形降维算法.该算法是基于投影度量，并且使用RCG（Riemannian conjugate gradient）算法优化目标函数，其在多个数据集上都取得了较好的实验结果，但是对于复杂的人脸数据集，如YTC其实验结果相对较差，只取得了66.69%的正确率.同时，RCG算法的时间效率较差.基于上述原因，提出了基于切空间判别学习的流形降维算法.该算法首先对于PML中的投影矩阵添加扰动，使其成为对称正定（symmetric positive definite，简称SPD）矩阵；然后，使用LEM（log-euclidean metric）将其映射到切空间中；最后，利用基于特征值分解的迭代优化算法构造判别函数，得到变换矩阵.对提算法在多个标准数据集上进行了实验验证，并取得了较好的实验结果，从而验证了该算法的有效性.

摘要:带通配符的模式匹配是一个经典的研究问题，带有可变间隙约束的模式匹配是近年来比较热门的研究方向.为适应某些查询精度要求较高的应用领域，提出一种在稀疏间隙约束条件下求解模式匹配完备解的算法SGPM-SAI（pattern matching with sparse gaps constraint based on suffix automaton index）.SGPM-SAI通过对文本串预处理，建立一种称为W-SAM的图索引结构，然后对模式串分段查找EndPos集合，最后以集合归并求交的方法得到模式匹配的完备解.实验结果表明：在不考虑预处理时间的情况下，相比几种最典型的模式匹配算法（KMP，BM，AC，suffix array），SGPM-SAI算法性能优势显著，至少高出3~5倍.通过与SAIL算法的最新优化版本（SAIL-Gen）进行比较，在稀疏间隙约束条件下，SGPM-SAI的性能要显著优于SAIL-Gen算法.此外，为有效利用现代处理器的大规模并行处理单元，提出了并行优化后的算法Parallel SGPM-SAI.实验结果表明：Parallel SGPM-SAI算法的加速效果显著，且具有良好的并行可扩展性，能够充分利用现代众核处理器的高并行计算优势.

摘要:近年来，为保护用户的隐私安全性，大量适用于全球移动网络环境的匿名漫游认证协议相继被提出.其中，部分协议采用临时身份代替真实身份的方法实现漫游过程中用户身份的匿名性需求，然而临时身份的重复使用，在一定程度上增加了用户的存储负担；部分协议采用身份更新的方法实现临时身份的一次一变性，但是相关信息的存储及更新操作，导致协议的执行效率较低.针对上述不足，提出模糊的直接匿名漫游认证协议.无需家乡代理的协助，通过1轮消息交互，外部代理即可直接完成对移动用户的身份合法性验证.同时，无需更新操作，即可实现漫游过程中临时身份的一次一变性.该机制在实现身份合法性匿名认证的同时，提高了协议的存储和执行效率，并且降低了通信时延.安全性证明表明，该协议在Canetti-Krawczyk（CK）安全模型下可证明是安全的.相较于传统漫游认证协议而言，该协议在存储、通信和计算等方面具有更优的性能，更适用于全球移动网络.

摘要:加密域水印技术适用于云环境下的隐私保护（加密）和数据安全认证（加水印）.通过结合保序加密、离散余弦变换、密码哈希和数字水印技术，提出了加密域数据库认证水印算法.首先对数据进行保序加密，以达到对敏感数据内容的隐私保护；对加密后的数据进行分组和离散余弦变换处理，然后将交流系数的哈希（Hashing）值作为认证信息嵌入到直流系数中来认证数据的完整性；可通过比对交流系数的哈希值和从直流系数中提取的水印信息，来判断加密数据是否受到篡改.水印嵌入设计很好地结合了保序加密的特性，使得对加密数据的水印嵌入不会影响到明文数据的正确恢复，利用密钥对加水印的加密数据库直接解密可得到原数据库.实验结果表明：所提出的算法不仅能够用于保护数据库中的内容隐私，而且能检测出不同程度的篡改和有效认证数据库数据的完整性.

摘要:域间路由系统是互联网的关键基础设施.针对域间路由系统的低速率拒绝服务攻击（low-rate DoS againstBGP sessions，简称BGP-LDoS）能够引起大范围级联失效，造成域间路由系统全局瘫痪.已有的防护机制和检测方法难以有效应对这种源自数据平面的大规模低速率流量拥塞攻击.分析域间路由系统在BGP-LDoS攻击威胁下的状态突变过程，提出一种基于突变平衡态理论（the equilibrium state of the catastrophe theory，简称ESCT）的BGP-LDoS攻击检测方法.以流量周期性特征、路由会话特征和报文转发量为检测特征进行突变模型的选择，并确定相应的状态变量和控制变量，进一步利用采集的历史数据为训练样本，对突变函数进行训练，以定义系统正常和失效状态时的平衡曲面.利用训练后的尖点突变模型对系统运行状态进行监控，根据分歧集函数判断系统是否出现由正常向失效的跳变，从而实现对攻击的检测.实验结果表明：ESCT方法仅需要监控系统中少量的关键链路和节点就能够具备较强的BGP-LDoS检测能力，为及时发现和提早应对攻击提供可靠参考.

摘要:无线可充电传感器网络（wireless rechargeable sensor networks，简称WRSN）中，如何调度移动充电器（mobile charger，简称MC），在充电过程中及时为传感器节点补充能量，尽量避免节点能量饥饿的同时降低MC充电代价及节点平均充电延迟，成为无线充电问题的研究挑战.大多数现有WRSN充电策略或是不能适应实际环境中传感器节点能量消耗的动态性和多样性，或是没有充分考虑节点及时充电问题和MC对充电响应的公平性，导致节点由于能量饥饿失效和充电策略性能下降.当网络中请求充电的节点数量较多时，节点能量饥饿现象尤为明显.为此，研究了WRSN中移动充电的能量饥饿问题，提出了能量饥饿避免的在线充电策略（energy starvation avoidance onlinecharging scheme，简称ESAOC）.首先，根据各节点能量消耗的历史统计和实时值计算当前能量消耗率.接着，在调度MC时，根据当前能量消耗率计算各请求充电节点的最大充电容忍延迟和当某节点被选为下一充电节点时各节点的最短充电等待时间，通过比较这两个值，始终选择使其他待充电节点饥饿数量最少的节点作为充电候选节点以尽量避免节点陷入能量饥饿.仿真分析表明：与现有几种在线充电策略相比，ESAOC不仅能有效解决节点的能量饥饿问题，同时具有较低的充电延迟和充电代价.

摘要:无线传感器网络广泛应用于人类社会生活的各个方面，例如灾难预警、工业控制等.而此类应用有很多不仅对数据的实时性存在较高要求，同时对鲁棒性也存在要求.此类问题主要挑战是要兼顾延迟性能和鲁棒性.针对这个挑战，提出了低延迟高鲁棒性的路由协议（RDR），RDR通过独特的路径探测寻找延迟较短、鲁棒性较强的路径，以此降低传输延迟，利用周围节点协助转发解决不稳定链路，增强鲁棒性，使得网络中的节点可以在良好的网络环境或恶劣的网络环境中都保持较好的延迟表现，同时保证网络中节点可以进行端到端通信，不再局限于单向数据收集.使用OMNeT++平台围绕延迟、鲁棒性等多个角度进行了大量的仿真实验，通过理论分析和仿真实验结合，从各个方面说明了所提协议可以保证较低的端到端延迟，并且具有很强的鲁棒性.

摘要:研究表明，网络中的故障不可避免而且频繁出现.当故障发生时，目前互联网部署的域内路由协议需要经历收敛过程.在此过程中，路由信息可能不一致，从而导致报文丢失，降低了路由可用性.因此，业界提出了利用LFA（loop free alternates）应对网络中发生的单故障情形，从而提高路由可用性.然而，已有的LFA实现方式算法时间复杂度大，需要消耗大量的路由器CPU资源.针对该问题严格证明了当网络中出现单故障时，只需要为特定的节点计算备份下一跳，其余受该故障影响节点的备份下一跳和该特定节点的备份下一跳是相同的.基于上述性质，分别讨论了对称链路权值和非对称链路权值中对应的路由保护算法.实验结果表明：与LFA相比较，该算法的执行时间降低了90%以上，路径拉伸度降低了15%以上，并且与LFA具有同样的故障保护率.

摘要:世界首台峰值性能超过100P的超级计算机——神威太湖之光已经研制完成，该超级计算机采用了国产申威异构众核处理器，该处理器不同于现有的纯CPU，CPU-MIC，CPU-GPU架构，采用了主-从核架构，单处理器峰值计算能力为3TFlops/s，访存带宽为130GB/s.稀疏矩阵向量乘SpMV（sparse matrix-vector multiplication）是科学与工程计算中的一个非常重要的核心函数，众所周知，其是带宽受限型的，且存在间接访存操作.国产申威处理器给稀疏矩阵向量乘的高效实现带来了很大的挑战.针对申威处理器提出了一种CSR格式SpMV操作的通用异构众核并行算法，该算法从任务划分、LDM空间划分方面进行精细设计，提出了一套动静态buffer的缓存机制以提升向量x的访存命中率，提出了一套动静态的任务调度方法以实现负载均衡.另外还分析了该算法中影响SpMV性能的几个关键因素，并开展了自适应优化，进一步提升了性能.采用Matrix Market矩阵集中具有代表性的16个稀疏矩阵进行了测试，相比主核版最高有10倍左右的加速，平均加速比为6.51.通过采用主核版CSR格式SpMV的访存量进行分析，测试矩阵最高可达该处理器实测带宽的86%，平均可达到47%.