摘要:研究k-SAT问题实例中每个变元恰好出现r=2s次，且每个变元对应的正、负文字都出现s次的严格随机正则（k，r）-SAT问题.通过构造一个特殊的独立随机实验，结合一阶矩方法，给出了严格随机正则（k，r）-SAT问题可满足临界值的上界.由于严格正则情形与正则情形的可满足临界值近似相等，因此得到了随机正则（k，r）-SAT问题可满足临界值的新上界.该上界不仅小于当前已有的随机正则（k，r）-SAT问题的可满足临界值上界，而且还小于一般的随机k-SAT问题的可满足临界值.因此，这也从理论上解释了在相变点处的随机正则（k，r）-SAT问题实例通常比在相应相变点处同规模的随机k-SAT问题实例更难满足的原因.最后，数值分析结果验证了所给上界的正确性.

摘要:为了刻画开放量子系统的量子属性，扩展现有的量子马尔可夫链是有必要的.通过构建Exogenous量子算子逻辑，定义了Exogenous量子马尔可夫链.作为新型量子马尔可夫链，重点研究了4种可达性公式，给出可达性公式可满足性问题的求解，并分析了它们的可判定性问题.作为应用，实例说明广义量子Loop程序的终止问题可以归结为Exogenous量子马尔可夫链的最终可达性，进而通过检测量子公式可满足性来判定程序的终止问题.

摘要:信息传播算法求解可满足问题时有惊人的效果，难解区域变窄.然而，因子图带有环的实例，信息传播算法不总有效，常表现为不收敛.对于这种现象，至今缺少系统的理论解释.警示传播（warning propagation，简称WP）算法是一种基础的信息传播算法，对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中，将警示信息的取值从{0，1}松弛为[0，1]，利用压缩函数的性质，给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟，结果表明：当子句与变元的比值α<1.8时，该判定条件有效.

摘要:软件持续演化已经是不争的事实，演化意味着需求的变化，也就必然导致了缺陷的不断产生.现有的缺陷预测技术多偏重于基于软件工作制品，如文档、代码、测试用例等的属性来预测缺陷，但如果把软件看作一种物种，其生命周期内的演化本质上是一个物种的逐步进化，其缺陷的表现也必然带着该物种的特征，而且还受到进化历史中的演化轨迹的影响.已有一些研究人员开始研究软件演化过程，并提出了一些演化度量元.研究和提出了可以刻画软件演化轨迹的两类演化度量元，并通过案例研究，建立缺陷预测模型.在6个著名开源软件数据集上训练和验证了由软件演化度量元建立的缺陷预测模型，获得了良好的预测性能，验证了演化度量元对缺陷预测性能的改进.

摘要:多尺度理论已被引入到数据挖掘领域，但人们对其研究仍不够深入和完善，缺乏普适性理论与方法.随着大数据处理应用的不断深入，其研究变得更加迫切.针对上述问题，进行了普适的多尺度数据挖掘理论和方法的研究.首先，基于概念分层理论给出了数据尺度划分和数据尺度的定义以及多尺度数据集之间的上下层尺度数据集关系；其次，阐明了多尺度数据挖掘的定义、研究实质和方法分类；最后，提出了多尺度数据挖掘算法框架，给出其理论基础，并将此框架应用于关联规则挖掘，提出了多尺度关联规则挖掘算法MSARMA（multi-scale association rules mining algorithm），实现了多尺度数据集之间知识的跨尺度推导.利用IBM T10I4D100K数据集和H省全员人口真实数据集对MSARMA算法进行了实验和分析，实验结果表明：算法具有较高的覆盖率、精确度和较低的支持度估计误差，是可行且有效的.

摘要:相似连接算法在数据清理、数据集成和重复网页检测等领域有着广泛的应用.现有相似连接算法有两种类型：基于相似度阈值的相似连接和Top-k相似连接.Top-k连接算法非常适合于相似度阈值未知的应用场景，目前最为有效的Top-k相似连接算法是Xiao等人提出的Topk-join.为了解决Topk-join中存在的性能问题，提出了一种Top-k相似连接算法Opt-join，该算法将Token批处理技术集成在现有的事件驱动框架中，以降低前缀事件的处理代价；通过置换哈希查找与过滤操作的执行位置来降低哈希查找代价，并理论证明了该置换的正确性.实验结果表明：与Topk-join算法相比，Opt-join取得了1.28倍~3.09倍的性能提升.实验数据还显示：随着数据长度的增加或k值的增长，Opt-join的性能优势有不断增加的趋势.

摘要:间隔查询作为重要的查询类型，广泛应用在社交网络、信息检索和数据库领域.为了支持高效的间隔查询，涌现出多种优化技术.尽管已有方法能够快速响应单个间隔查询，然而当查询负载超过服务器的处理能力时，70%的查询均不能在期望时间内得到响应.针对这一问题，提出采用共享执行策略优化间隔查询的方法SESIQ（shared execution strategy for interval queries）.SESIQ对间隔查询进行批处理，分析一组间隔查询间可共享的操作，减少重复数据的访问，从而降低磁盘I/O和网络传输代价，提高检索性能.理论分析并实验验证了SESIQ的可行性，基于两种真实数据集的大量实验结果表明，SESIQ是有效的，间隔查询的检索性能可提升数十倍.

摘要:在无线传感器网络所面临的安全问题中，虫洞攻击是最严重的威胁之一.由于无线传感器节点的资源非常有限，因此，适用于有线网络上的基于密码学的安全技术不能直接移植于无线传感网络.目前已知的传感网中，虫洞攻击的探测方案在应用上存在问题，这些方案或需要精确时间同步、或额外的定位算法或硬件、或有较大的通信开销，并且，现有方案均不能检测可自适应调整攻击策略的主动虫洞敌手.结合无线传感器网络的特点，提出了基于拓扑的被动式实时虫洞攻击探测方案，称为Pworm.通过利用虫洞攻击的主要特征——大量吸引网络流量和显著缩短平均网络路径，Pworm不需要任何额外的硬件，只需要收集网络中部分路由信息，就能实时地探测虫洞节点，即使是主动虫洞节点，也不能通过改变自身攻击策略而躲避探测.实验结果和分析表明：该方案具有轻量级、低漏报率、高可扩展性等优点，适用于大规模无线传感网络.

摘要:软件定义网络的出现为防御DDoS攻击提供了新的思路.首先，从网络体系结构角度建模分析了DDoS攻击所需的3个必要条件：连通性、隐蔽性与攻击性；然后，从破坏或限制这些必要条件的角度出发，提出了一种能够对抗DDoS攻击的软件定义安全网络机制SDSNM（software defined security networking mechanism）.该机制主要在边缘SDN网络实现，同时继承了核心IP网络体系架构，具有增量部署特性.利用云计算与Chord技术设计实现了原型系统，基于原型系统的测量结果表明，SDSNM具有很好的扩展性和可用性.

摘要:有向传感器网络由大量有向传感器节点组成，不同于有着全向感知范围的全向传感器网络，有向传感器网络的感知范围是一个扇形区域.研究了有向传感器网络的覆盖预测模型及数量估计问题.针对节点随机部署的应用环境，在初始部署网络时，为满足一定的覆盖率要求，在充分考虑了目标区域边界效应的基础上，提出了一种基于概率的网络覆盖预测模型.基于该模型，对初始部署的节点数目进行了预测.通过仿真实验，对结果进行了分析.结果表明：利用所提模型得到的理论值与实验真实值拟合较好，且更符合实际应用需求.

摘要:将目标形状的轮廓看成一个无序的点集，从中抽取形状特征，用于快速而有效的目标识别是形状分析任务中的挑战性问题.针对该问题，提出了一种基于复杂网络模型的形状描述和识别方法.该方法提出用一种自组织的网络动态演化模型构成一个分层的描述框架，在网络动态演化的每一个时刻，对网络分别进行局部测量和全局测量，抽取网络的无权特征和加权特征.在形状匹配阶段，用获得的局部描述子和全局描述子分别进行局部匹配（基于Hausdorff距离）和全局匹配（基于L₁距离），组合两种匹配的距离值构成对形状的差异度度量.用标准的测试集对所提出的方法进行性能测试，实验结果表明，所提出的算法能够快速而又鲁棒地完成较高精度的形状识别任务.

摘要:由于系统的巨大规模，操作系统设计和实现的正确性很难用传统的方法进行描述和验证.在汇编层形式化地对系统模块的功能语义进行建模，提出一种汇编级的系统状态模型，作为汇编语言层设计和验证的纽带.通过定义系统状态模型的合法状态和状态转换函数来建立系统状态模型的论域，并以此来描述汇编层的论域.通过验证汇编层的功能模块的正确性来保证汇编语言层设计的正确性，达到对系统功能实现的正确性验证.同时，使用定理证明工具Isabelle/HOL来形式化地描述这一系统状态模型，基于这一形式化模型，在Isabelle/HOL中验证系统模块的功能语义的正确性.以实现的安全可信OS（verified secure operating system，简称VSOS）为例，阐述了所提出的形式化设计和验证方法，说明了这一方法的可行性.

摘要:容错是硬实时系统的关键能力，容错调度算法可以在有错误发生的情况下满足任务的实时性需求.在主副版本机制的容错调度算法中，主版本出错后留给副版本运行的时间窗口小，副版本容易错失截止期.针对副版本需要快速响应的问题，提出副版本不可抢占的全局容错调度算法FTGS-NPB（fault-tolerant global scheduling with non-preemptive backups），赋予副版本全局最高优先级，使副版本在主版本出错后可以立刻获得处理器资源，并且在运行过程中不会被其他任务抢占.这样，副版本可以在最短时间内响应.分别基于截止期分析和响应时间分析建立了FTGS-NPB的可调度性测试，并分析了两种可调度性测试分别适用于不同的优先级分配算法.仿真实验结果表明，FTGS-NPB可以有效地减少实现容错的代价.

摘要:内核恶意软件对操作系统的安全造成了严重威胁.现有的内核恶意软件检测方法主要从代码角度出发，无法检测代码复用、代码混淆攻击，且少量检测数据篡改攻击的方法因不变量特征有限导致检测能力受限.针对这些问题，提出了一种基于数据特征的内核恶意软件检测方法，通过分析内核运行过程中内核数据对象的访问过程，构建了内核数据对象访问模型；然后，基于该模型讨论了构建数据特征的过程，采用动态监控和静态分析相结合的方法识别内核数据对象，利用EPT监控内存访问操作构建数据特征；最后讨论了基于数据特征的内核恶意软件检测算法.在此基础上，实现了内核恶意软件检测原型系统MDS-DCB，并通过实验评测MDS-DCB的有效性和性能.实验结果表明：MDS-DCB能够有效检测内核恶意软件，且性能开销在可接受的范围内.

摘要:请求负载均衡，是分布式文件系统元数据管理需要面对的核心问题.以最大化元数据服务器集群吞吐量为目标，在已有元数据管理层之上设计实现了一种分布式缓存框架，专门管理热点元数据，均衡不断变化的负载.与已有的元数据负载均衡架构相比，这种两层的负载均衡架构灵活度更高，对负载的感知能力更强，并且避免了热点元数据重新分布、迁移引起的元数据命名空间结构被破坏的情况.经观察分析，元数据尺寸小、数量大，预取错误元数据带来的代价远远小于预取错误数据带来的代价.针对元数据的以上鲜明特点，提出一种元数据预取策略和基于预取机制的元数据缓存替换算法，加强了上述分布式缓存层的性能，这种两层的元数据负载均衡框架同时考虑了缓存一致性的问题.最后，在一个真实的分布式文件系统中验证了框架及方法的有效性.

摘要:随着软件系统功能和性能的强化和提高，企业的管理效率在不断提升，运营模式也越来越丰富.与此同时，软件系统变得越来越复杂，这向软件系统管理和维护提出了严峻的挑战.如何通过采集系统外部特征参数，对系统内部状态进行客观、准确地评估和预测，成为亟待解决的问题.为此，提出了一种基于隐马尔可夫模型的软件系统状态评估预测方法.该方法基于软件系统外在特征参数，通过K-means方法构建系统的观测状态，并以此建立隐马尔可夫模型，建立起系统外在状态（观测状态）和内部状态（隐藏状态）之间的联系；再利用三次指数平滑法对具有周期性变化的系统特征参数进行预测，即可预测系统未来状态.针对基于B/S软件架构的信息管理系统的实验，其结果表明该方法对系统状态评估和预测具有较高的准确性.