基于SAT的GRANULE算法不可能差分分析

基于布尔可满足性问题(SAT)的自动化搜索方法可以直接刻画与、或、非、异或等逻辑运算,从而建立更高效的搜索模型。为更高效地评估GRANULE算法抵抗不可能差分攻击的能力,首先,基于S盒差分分布表性质优化S盒差分性质刻画的SAT模型;其次,对GRANULE算法建立基于比特的不可能差分区分器的SAT模型,通过求解模型得到多条10轮GRANULE算法的不可能差分区分器;再次,针对不可能差分区分器,给出改进的SAT自动化验证方法并验证;最后,将得到的区分器往前和往后各扩展3轮,对GRANULE-64/80算法发起16轮的不可能差分攻击,通过该攻击可以恢复80比特主密钥,时间复杂度为251.8次16轮加密,数据复杂度为241.8个选择明文。与表现次优的对GRANULE算法不可能差分分析的方法相比,所得到的区分器轮数和密钥恢复攻击轮数都提高了3轮,且时间复杂度、数据复杂度都进一步下降。

VDE-SAT下行链路信道建模方法

海面的散射特性导致VDES海上通信信道模型复杂多变,在VDE-SAT下行链路中,低仰角通信导致海浪反射带来的多径效应更加严重。针对此问题,提出一种基于球坐标系的VDE-SAT下行链路信道建模方法,根据不同海情级分析海浪反射对于信号接收特性的影响。首先,将海面散射特性的统计结果参数化,结合地球曲率的影响,建立基于球坐标系的星船通信几何模型,基于此,得到海面有效漫反射区。其次,建立星船通信链路的信号多径传播模型,基于G1139协议,根据各个路径的信道参数分析接收信号的功率分布,以及不同海情级下信号的接收特性。仿真结果表明:在海况较好时,该多径信道以镜面反射为主;海况较差时,以漫反射为主。相比于卷积码,Turbo码的抗多径性能更优。

完全匹配层在矩阵式波动方程SBP-SAT方法应用

数值离散方法和截断边界效果是地震动模拟实现的关键。基于分部求和(summation-by-parts,SBP)和一致逼近(simultaneous approximation term,SAT)的SBP-SAT方法具有较高的稳定性,这使得该方法具备了较高的应用前景和价值。此外,完全匹配层(perfect matching layer,PML)是一种应用广泛用于模拟截断边界的技术,但引入匹配层可能会破坏原始方程的稳定性,特别是在各向异性介质或曲线域模型中。首先基于数理推导,给出弹性波动方程系数矩阵的对称形式。在此基础上,引入多轴完全匹配层(multi-axis perfect matching layer,MPML),并建立相应的匹配层方程。通过本征值分析,我们可以判断阻尼函数对原方程特征根实部的走向和取值范围的影响。然后,我们采用SBP-SAT方法对矩阵对称形式匹配层方程进行离散,并在频域中采用能量法进行稳定性评估。通过对不同模型的数值仿真,表明所提出的离散框架具有整合度高、稳定性好和拓展性强等特点。此外,多轴匹配层可以与SBP-SAT方法结合,可以稳定地模拟曲线域中的波传播。

SAT-TB、Xpert-MTB/RIF对复治肺结核患者快速诊断的应用价值

目的 探讨分枝杆菌RNA恒温扩增实时检测技术(SAT-TB)、Xpert-结核分枝杆菌/利福平耐药检测(Xpert-MTB/RIF)对复治肺结核患者快速诊断的应用价值。方法 选取2019年1月至2019年12月在广州市胸科医院疑似复治肺结核患者319例,收集痰或支气管肺泡灌洗液标本,分别采用涂片找抗酸杆菌、分枝杆菌培养法、SAT-TB法及Xpert-MTB/RIF法检测,统计分析各检测方法对复治肺结核诊断的灵敏度、特异度、准确率、阳性预测值及阴性预测值。结果 319例患者中最终确诊92例复治肺结核患者,其他非活动性肺结核患者227例;以临床最终诊断为标准评估各指标诊断价值,在复治肺结核患者的诊断灵敏度上,Xpert-MTB/RIF法最高,涂片法最低,差异有统计学意义(χ^(2)=26.302,P<0.05);特异度以SAT-TB法最高,差异有统计学意义(χ^(2)=33.675,P<0.05);诊断准确率方面SAT-TB法与Xpert-MTB/RIF法差异无统计学意义(χ^(2)=0.960,P=0.327),但均显著高于涂片法与分枝杆菌培养法,差异有统计学意义(χ^(2)=22.756,P<0.05);阳性预测值以SAT-TB法最高,差异有统计学意义(χ^(2)=23.435,P<0.05);阴性预测值方面Xpert-MTB/RIF法与分枝杆菌培养法差异无统计学意义(χ^(2)=3.159,P=0.076),但显著高于另外2种检测方法,差异有统计学意义(χ^(2)=19.499,P<0.05)。结论 SAT-TB法对复治肺结核患者具有极高的特异度与准确率,且阳性预测价值高,临床可减少误诊,Xpert-MTB/RIF法具有高灵敏度,临床联合应用可避免漏诊误诊。

TI介质中P-SV波传播的SBP-SAT模拟

基于速度-应力形式的弹性波动方程,采用分部求和和同时逼近项技术建立的SBP-SAT方法,推导了横向各向同性(transversely isotropy,TI)介质的矩阵对称型(symmetric matrix form,SMF)弹性波动方程离散形式,并通过能量法进行了稳定性分析。将该方法应用于倾斜横向各向同性(tilted transverse isotropic,TTI)介质模型、垂直横向各向同性(transverse isotropy with a vertical axis of symmetry,VTI)介质和含裂缝及曲线域的复杂介质模型,对所得的速度幅值和单炮记录分析并总结规律;对不同时间步长、单元网格数的结果进行对比,得出计算效率并验证该方法在求解P-SV波传播问题上的正确性。数值模拟结果表明,该方法模拟精度高,适用性好,在地震数值模拟领域有很好的应用价值和前景。

肺泡灌洗液TB-SAT快速诊断涂阴肺结核价值的研究

目的探究肺泡灌洗液结核分枝杆菌RNA恒温扩增荧光实时检测技术(TB-SAT)诊断涂阴肺结核诊断的价值。方法选取2022年1月至7月江西省胸科医院收治的60例疑似肺结核患者,将综合诊断结果(符合肺结核基层诊疗指南)设为金标准,进行肺泡灌洗液TB-SAT,分析价值。结果60例患者中,46例患者诊断为肺结核,剩余14例为其他疾病。在46例经金标准诊断为肺结核的患者中,支气管肺泡灌洗液(BALF)抗酸染色诊断9例为肺结核患者;BALF结核菌培养诊断14例为肺结核患者;BALF聚合酶链式反应(PCR)检测诊断21例为肺结核患者;BALF TB-SAT诊断30例为肺结核患者。BALF抗酸染色诊断结果:敏感度为19.57%(9/46)、特异度为57.14%(8/14)、准确度为28.33%(17/60);BALF结核菌培养诊断结果:敏感度为30.43%(14/46)、特异度为78.57%(11/14)、准确度为41.67%(25/60);BALF PCR诊断结果:敏感度为45.65%(21/46)、特异度为64.29%(9/14)、准确度为50.00%(30/60);BALF TB-SAT诊断结果:敏感度为65.22%(30/46)、特异度为92.86%(13/14)、准确度为71.67%(43/60)。BALF TB-SAT诊断结果敏感度、准确度高于其他检测方法,差异有统计学意义(P<0.05);不同检测方法的特异度比较,差异无统计学意义(P>0.05)。结论诊断涂阴肺结核患者时,利用肺泡灌洗液TB-SAT具有较高价值,临床效果显著。

基于改进型SAT求解器算法的组合电路等价性检查研究

随着工艺节点的缩小,集成电路规模的增加,集成电路设计过程中逻辑等价性检查在确保设计功能正确性方面起着重要作用。文章研究了组合电路逻辑等价性检查技术,针对该领域常用的DPLL和CDCL算法存在的问题,提出了一种基于蒙特卡洛树搜索的改进算法。通过对ISCAS85测试集的一个子集的实验,证实该算法对CDCL算法有一定的改进,应用于组合电路等价性检查的平均运行时间减少了20%。

美国学术能力评估测试的存废之争及其启示

鉴于“肯定性行动”取消导致弱势群体录取比例下降、学术能力评估测试筛选功能需求降低以及高等教育机构利益受到影响,美国众多院校不再强制要求学生提交标准化考试成绩。这一招生政策的调整引发学界和社会的广泛关注,美国学术能力评估测试存废问题成为争论焦点。持否定观点者质疑SAT的公平性和有效性,认为标准化考试成绩和考生的社会经济地位有着显著的相关性等;持肯定观点者认为,SAT成绩是美国绝大部分高校开展招生录取工作的重要依据,在维护弱势群体利益等方面发挥了重要作用。在回顾美国SAT存废之争的基础上,客观分析这一论争的深层原因,为我国高考改革提供一些启示。

基于SPARTA框架的HAS4决赛攻击路径分析

太空网络面临的安全威胁越来越多,美国自2020年起,连续四年举办黑掉卫星(Hack-A-Sat,HAS)挑战赛,并发射真实卫星“月光者”用于HAS比赛。太空攻击研究与战术分析框架SPARTA是针对太空网络安全的对抗战术和技术知识库。借助SPARTA框架,详细分析了第四届HAS决赛中攻击使用的战术技术,对于深入理解SPARTA框架、太空网络安全具有一定借鉴意义。

求解SAT问题的拟人退火算法

该文利用一个简单的变换 ,将可满足性 (SAT)问题转换为一个求相应目标函数最小值的优化问题 ,提出了一种用于跳出局部陷阱的拟人策略 .基于模拟退火算法和拟人策略 ,为 SAT问题的高效近似求解得出了拟人退火算法 (PA) ,该方法不仅具有模拟退火算法的全局收敛性质 ,而且具有一定的并行性、继承性 .数值实验表明 ,对于本文随机产生的测试问题例 ,采用拟人策略的模拟退火算法的结果优于局部搜索算法、模拟退火算法以及近来国际上流行的 WAL KSAT算法 。

组织进化算法求解SAT问题

基于组织的概念设计了一种新的进化算法———求解SAT问题的组织进化算法 (OrganizationalEvolution aryAlgorithmforSATproblem ,OEASAT) .OEASAT将SAT问题分解成若干子问题 ,然后用每个子问题形成一个组织 ,并根据SAT问题的特点设计了三种组织进化算子———自学习算子、吞并算子和分裂算子以引导组织的进化 .根据组织的适应度 ,将所有组织分成两个种群———最优种群和非最优种群 ,然后用进化的方式来控制各算子 ,以协调各组织间的相互作用 .OEASAT通过先解决子问题 ,再协调相冲突变量的方式来求解SAT问题 .由于子问题的规模较小 ,相对于原问题来说较容易解决 ,这样就达到了降低问题复杂度的目的 .实验用标准SATLIB库中变量个数从 2 0～ 2 5 0的 370 0个不同规模的标准SAT问题对OEASAT的性能作了全面的测试 ,并与著名的WalkSAT和RFEA2的结果作了比较 .结果表明 ,OEASAT具有更高的成功率和更高的运算效率 .对于具有 2 5 0个变量、10 6 5个子句的SAT问题 ,OEASAT仅用了 1.5 2 4s,表现出了优越的性能 .

一种计算ARX密码差分—线性偏差的新方法

ARX密码由模加、循环移位和异或这3种基本运算组成。目前ARX密码差分—线性区分器偏差的计算大多采用统计分析的方法。在2022年美密会上,NIU等给出了一种计算ARX密码差分—线性区分器相关度的非统计分析的方法,并给出了SPECK32/64的10轮差分—线性区分器。基于BLONDEAU等和BAR-ON等的方法,给出了差分—线性特征的定义,并首次提出了用差分—线性特征计算差分—线性区分器偏差的方法。同时,提出了一种基于布尔可满足性问题(SAT)自动化技术搜索差分—线性特征的方法,给出了计算ARX密码差分—线性区分器偏差的非统计分析的新方法。作为应用,对NIU等给出的SPECK32/64的10轮差分—线性区分器偏差进行计算,得到的理论值为2-15.00,非常接近统计分析的实验值2-14.90,且优于NIU等给出的理论值2-16.23。同时,首次给出了SIMON32/64的9轮差分—线性区分器偏差的理论值2-8.41,接近统计分析得到的实验值2-7.12。实验结果说明了这种方法的有效性。

基于子句权重学习的求解SAT问题的遗传算法

该文提出了一种求解SAT问题的改进遗传算法(SATWAGA).SATWAGA算法有多个改进性特点:将SAT问题的结构信息量化为子句权重,增加了学习算子和判定早熟参数,学习算子能根据求解过程中的动态信息对子句权重进行调整,以便防止遗传进程的早熟,同时,算法还采用了最优染色体保存策略,防止进化过程的发散.该文最后描述了实现包括SATWAGA等多个算法的实验系统,对选择最佳早熟判定参数值给出了一些有效的建议.实验结果表明:与一般遗传算法相比,SATWAGA算法在求解速度、成功率和求解问题的规模等方面都有明显的改善.

求解SAT问题的量子免疫克隆算法

将量子计算应用于人工免疫系统中的克隆算子,提出了一种基于量子编码的免疫克隆算法(Quantum-InspiredImmuneClonalAlgorithm,QICA)来求解SAT问题,并从理论上证明了算法的全局收敛性.算法中采用量子位的编码方式来表达种群中的抗体,针对这种编码方式采用量子旋转门和动态调整旋转角度策略对抗体进行演化,加速原有克隆算子的收敛;利用克隆算子的局部寻优能力强的特点,在各个子群体间采用量子交叉操作来增强信息交流,提高种群的多样性防止早熟.实验中,用标准SATLIB库中的3700个不同规模的标准SAT问题对QICA的性能作了全面的测试,并与单纯的量子遗传算法和简单免疫克隆算法以及著名的WalkSAT和PFEA2算法进行比较,仿真实验表明:QICA具有更高的成功率和运算效率.对于具有250个变量、1065个子句的SAT问题,QICA也仅用了1.357s,显示出了优越的性能.

利用近似解加速求解SAT问题的启发式完全算法

结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策.该算法引导完全算法优先搜索近似解所在的子空间,加速解决器找到可满足解的过程,为SAT问题的求解提供了一种新的有效途径.实验结果表明,该算法有效地提高了决策的精度和SAT解决器的效率,对很多实例非常有效.

一种基于SAT的运算电路查错方法

基于SAT的运算电路查错方法将被验证系统中系统规范成立与否的问题转换为布尔公式和数学公式的混合形式E-CNF,通过采用了标志子句技术的E-SAT求解器进行求解.实验表明该方法自动化程度高,能处理大规模的运算电路,有较强的查找错误能力.

大数据动态安全SAT双向防御模型的研究

为了保障大数据计算的安全,结合大数据安全的安全研究和可信云的概念,提出一个大数据计算下SAT的双向防御系统模型。该模型通过动态安全因子对用户数据证据进行规范;逐步确定各行为证据的安全权限,实现行为的可靠性测试,为用户提供最大限度的安全防御。实验结果表明,该系统模型可以有效地提升大数据的数据安全,降低黑客的恶意攻击行为,从而提高大数据分析效率。

使用SAT求解器产生所有极小冲突部件集

产生所有的极小冲突部件集为基于模型诊断中的一个重要步骤.本文将待诊断系统的行为模型及观测分别使用合取范式(CNF)形式的文件描述,从而提出将判定系统组件子集是否为冲突集的问题转化为:首先提取相关组件的CNF模型及观测,然后调用成熟的SAT求解器判定可满足性.随后,通过有效地结合CSISE-tree等方法来产生所有的极小冲突集.为进一步提高效率,给出了充分利用系统输入/输出结构信息的启发式策略.实验结果表明,使用结合SAT求解器及CSISE-tree等方法能够较快产生所有极小冲突集,并且启发式策略使得求解效率进一步提高(平均提高约21%,最高者甚至达到约48%).

SAT问题中局部搜索法的改进

局部搜索方法在求解SAT问题的高效率使其成为一研究热点.提出用初始概率的方法对局部搜索算法中变量的初始随机指派进行适当的约束.使在局部搜索的开始阶段,可满足的子句数大大增加,减少了翻转的次数,加快了求解的速度.用该方法对目前的一些重要的SAT问题的局部搜索算法(如WSAT,TSAT,NSAT,SDF等)进行改进,通过对不同规模的随机3-SAT问题的实例和一些不同规模的结构性SAT问题的实例,以及利用相变现象构造的难解SAT实例测试表明,改进后的这些局部搜索算法的求解效率有了很大的提高.该方法对其他局部搜索法的改进具有参考价值。

最坏情况下#3-SAT问题最小上界

最坏情况下#SAT问题上界的研究已成为一个热门的研究领域.#SAT问题的时间复杂性是根据问题实例的大小所组成的函数计算所得.#SAT问题实例的大小不仅依赖于变量的数量,还依赖于子句的数量.以子句数量为参数研究#SAT问题在最坏情况下的上界,不仅可以从另一个角度衡量算法的好坏,而且在某种程度上更能准确地反映出算法的性能.首先从子句数量的角度证明了之前提出的基于扩展规则的模型计数算法(CER算法)的上界O(2m),其中m是公式中子句的数量.为了提高#3-SAT问题的求解效率,采用了多种分裂规则,进一步给出了一种基于Davis-Putnam-Logemann-Loveland(DPLL)的#3-SAT算法MCDP.通过分析该算法得到了以子句数量为参数的#3-SAT问题在最坏情况下的上界O(1.8393m).