基于充分统计量的数据复杂度增量学习方法研究

数据复杂度是衡量数据类别可分性的指标,能够对数据预处理、分类器选择等环节提供有效的指导信息。但现有的数据复杂度计算方法不具备增量学习的功能,从而限制了它们的实际应用。研究结果表明可以通过计算充分统计量来实现增量学习功能的4个数据复杂度指标。实验结果验证,这些数据复杂度指标增量学习的有效性。

基于数据复杂度的投毒数据检测方法

针对机器学习模型训练过程中攻击者可以利用修改原始训练数据生成投毒数据的方式对机器学习模型进行投毒攻击的问题,提出一种基于数据复杂度的投毒数据检测方法。该方法在正常数据集的基础上,应用梯度上升策略对正常数据集内的样本实例进行自我投毒,通过挖掘自我投毒产生的投毒数据对正常数据集数据复杂度的影响,训练能够辨别投毒数据的检测模型。该方法在选定应用场景中的检测准确率比现有方法有更好的效果。实验结果表明,投毒数据能够有效降低机器学习模型预测能力,应用基于数据复杂度的检测方法能够有效检测投毒数据,降低投毒数据对模型预测能力的不良影响。

基于数据复杂性的信息系统复杂度测量方法的有效性验证

考虑到基于数据复杂性的信息系统复杂度测量方法提出的时间短、应用案例较少,通过对相同案例的应用研究,将该方法与基于功能分解角度的信息系统体系结构复杂度测量方法进行比较,验证了基于数据复杂性的信息系统复杂度测量方法的有效性。比较分析的结果表明,该方法相较于传统信息系统复杂度测量方法,具有测量模型更加全面、测量方法的动态性考虑更充分等优势。

面向文本语料库的数据模型及其查询问题

语料库为语言研究和自然语言处理提供基础数据服务.传统语料库数据缺乏规范的数据模型,导致无法科学的评价查询结果,大大降低了数据可用性.针对该问题,提出一种面向语料库的数据模型,并讨论了其上的查询问题.首先,给出语料库数据的形式化定义,其次,在关系模型的基础上提出一种面向文本语料库的数据模型,并证明了模型的完备性,在此基础上,扩展传统语料库以KWIC(Key Word In Context)输出为中心的查询语义,定义了语料库数据的查询问题KWIC-EXTENTION.最后,证明这些查询问题的数据复杂度,其中,正匹配查询、负匹配查询、析取匹配查询、n-临近匹配查询的数据复杂度是AC0的,临近正匹配查询的数据复杂度是PTIME(Polynomial Time)的,临近负匹配查询问题的数据复杂度是PSPACE(Polynomial Space)的.这些结论为语料库数据模型和查询方法的研究奠定了理论基础.

移动数据库视图更新算法研究

由于移动无线网络的不稳定特性,有必要在移动主机端缓存数据。在移动数据库应用中,数据缓存采取实体化视图形式,由位于固定网络中的视图管理器来维护。为了减少无线传输量,使用视图增量更新算法。但是当网络带宽不足时,只能选择一部分增量进行更新。于是有人提出了根据动态的数据新鲜度优先级进行排队的视图更新算法PIU算法,但是这种算法仅仅考虑了视图整体数据的动态新旧度,即平均时间因素,所以仍存在许多缺陷。为了弥补这些缺陷,在这基础上,引入用户的访问概率和数据的复杂度两个因素,提出改进的PIU算法,有效地改善移动数据库视图更新的面向用户性、实时性和一致性。

k-匿名隐私保护模型中不确定性数据的查询问题

查询是一种重要的数据库操作。在k-匿名隐私保护模型中,每条元组不仅包括精确数据,还包括泛化数据,因此k-匿名数据是一种不确定数据。为了讨论k-匿名数据的查询问题,首先,提出一种描述k-匿名数据的不确定性数据模型,在此基础上,定义了k-匿名数据的成员(Membership)问题、可能性(Possibility)问题、确定性(Certainty)问题、包含(Containment)问题等查询问题,然后,讨论了这些问题的数据复杂度,证明了Membership问题是PTIME,q-Membership问题是NP-完全的,q′-Containment问题是Πp 2-完全的,q-Containment问题coNP-完全的,Possibility问题是PTIME,q-Possibility问题是NP-完全的,Certainty问题是coNP-完全的。这些结论为k-匿名隐私保护模型中不确定性数据查询方法的研究奠定了理论基础。

基于迭代延长纠错输出编码的微阵列数据多分类方法

微阵列技术使快速大量检测基因成为可能,人们迫切需要利用该技术提高疾病诊断水平.因此,对微阵列数据的分析研究迅速发展,其中以数据多类分类研究尤为突出.但由于微阵列数据具有特征多、样本少的特点,使得传统统计学习方法分类效果欠佳.为了针对微阵列数据特点解决多类分类问题,提出了一种迭代延长纠错输出编码(iterative extension error correct output coding,IE-ECOC)的算法.在几个特征子集上,配合与特征相关的数据复杂度,利用一种基于二叉树的编码方法生成一个列池,并提出一种择列策略构造编码矩阵;然后,依据迭代验证结果延长矩阵.对癌症基因微阵列进行分类实验,结果显示,IE-ECOC对特征多、样本少的数据具有针对性,且与一些经典的ECOC算法相比,可以产生较好的结果,IE-ECOE算法效果也在实验中得到了验证.

对全轮AES-128算法的低数据Biclique攻击

直到Biclique分析方法的出现,才有了在单密钥模式下对AES-128算法的全轮攻击,但初始的数据复杂度较高。文章采取分割末尾轮密钥空间的方式,构造一个新的Biclique结构,使得数据复杂度从2^(88)个选择密文降为2~8个选择密文。

轮函数未知的三分支广义Feistel结构的YOYO攻击

将YOYO攻击用于轮函数未知的三分支广义Feistel结构。首先构造了7轮的差分特征,利用这一差分特征构造了明密文方程,成功恢复了第6轮的未知轮函数。攻击的时间和存储复杂度都是2n+1,数据复杂度为1个明文对。

低轮MIBS分组密码的积分分析

分组密码算法MIBS是轻量级密码算法,其设计目标是适用于RFID和传感等资源受限的环境.对其进行了积分分析,给出了一个5轮的积分区分器,并利用高阶积分的技术将该5轮区分器向前扩展了3轮.据此对MIBS进行了8轮、9轮和10轮的攻击.8轮攻击数据复杂度为29.6,时间复杂度为235.6次加密;9轮的攻击数据复杂度为237.6,时间复杂度为240次加密;10轮的攻击数据复杂度为261.6,时间复杂度为240次加密.同时该攻击结果适用于MIBS-64和MIBS-80两个版本.研究结果表明,这种所使用的高阶积分技术对于Feistel-SP结构的分组密码普遍适用.

22-轮SMS4的差分分析

SMS4是中国官方公布的第一个商用分组密码标准,使用差分方法分析了18轮的SMS4差分特征,并在此基础上攻击了22-轮的SMS4,攻击过程需要2117个选择明文,2112字节的存储空间,而时间复杂度为2123次22-轮加密。此结果是目前对SMS4差分分析的最好结果。

低轮FOX分组密码的碰撞-积分攻击

FOX是最近推出的系列分组密码,它的设计思想基于可证安全的研究结果,且在各种平台上的性能优良.本文利用碰撞攻击和积分攻击相结合的技术分析FOX的安全性,结果显示碰撞-积分攻击比积分攻击有效,攻击对4轮FOX64的计算复杂度是245.4,对5轮FOX64的计算复杂度是2109.4,对6轮FOX64的计算复杂度是2173.4,对7轮FOX64的计算复杂度是2237.4,且攻击所需数据量均为29;也就是说4轮FOX64/64、5轮FOX64/128、6轮FOX64/192和7轮FOX64/256对本文攻击是不免疫的.

对LBlock算法的多重零相关线性分析

为了降低对LBlock进行零相关线性分析所需的数据复杂度,提出了对LBlock进行多重零相关线性分析的方法,证明了14轮LBlock存在26条零相关线性逼近,并给出了其具体构造.利用26条14轮零相关线性逼近为区分器,并基于正态分布的概率计算模型对22轮LBlock进行了多重零相关线性攻击,攻击的数据复杂度约为263.45个已知明文,计算复杂度约为276.27次22轮LBlock加密,成功实施攻击的概率为0.85.结果表明,该方法有效解决了需要利用整个明文空间对LBlock进行零相关线性分析的问题.

Zodiac算法的碰撞攻击

为了研究Zodiac算法抵抗碰撞攻击的能力,根据算法的一个等价结构,分别给出了Zodiac算法的两个8轮和9轮区分器。通过在此区分器前后加适当的轮数,首先,利用9轮区分器对12轮到16轮的算法进行了碰撞攻击,其攻击的数据复杂度分别为215,231.2,231.5,231.7,263.9,时间复杂度分别为233.8,249.9,275.1,2108,2140.1;其次,利用8轮区分器对全轮算法进行了攻击,其攻击的数据复杂度和时间复杂度分别为260.6和2173.9。结果表明:全轮的Zodiac-192/256算法均不能抵抗碰撞攻击。

轻量级分组密码PRINCE算法的Biclique分析

PRINCE算法是Rechberger等人在2012年亚密会上提出的一个对合轻量级分组密码算法,广泛应用于资源受限的设备.PRINCE算法的分组长度为64比特,密钥长度为128比特.算法基于FX结构,一部分密钥用于核心算法PRINCEcore,剩余的密钥用作PRINCEcore前后的白化密钥.PRINCEcore算法也是一个分组密码算法,保持PRINCE算法主要的加密过程.Biclique分析是一种新的分组密码分析方法,受到密码学者的广泛关注.Abed等人利用Biclique攻击方法给出了全轮PRINCEcore算法的攻击结果,计算复杂度为2^(62.72)次加密,数据复杂度为2^(40)个选择密文.受其启发,我们也给出了PRINCE算法抗两类Biclique分析的结果.本文中,我们首先介绍了平衡Biclique和星型Biclique的结构,以及Biclique密码分析的一般流程;其次,我们简单介绍了PRINCE算法的结构.然后,我们对Abed的方法进行改进,构建了一个1轮的平衡Biclique结构,计算复杂度为2^(62.69),数据复杂度为2^(32)个选择明文,二者均优于之前的攻击结果.最后,我们也构建了一个基于星型的Biclique结构,攻击的计算复杂度为2^(63),而数据复杂度仅需一个明密文对,这是目前为止对PRINCEcore算法全轮分析数据复杂度最优的分析结果.

基于卡方统计量的多差分攻击方法

为了精确地估计分组密码算法抵抗差分攻击的能力,在已知多个具有高概率差分特征的条件下,提出了基于卡方统计量的多差分攻击方法.分析了正确密钥和错误密钥对应的统计量的分布规律,给出了多差分攻击方法的成功率、数据复杂度和计算复杂度的关系.在分组密码算法的差分特征概率未知的条件下,该方法仍然是适用的.

ARIA分组密码算法的不可能差分攻击

ARIA密码是2003年由韩国学者提出,并在2004年被选为韩国分组密码标准的新的分组密码算法.为了使用不可能差分方法对ARIA密码算法进行安全性分析,首先,根据ARIA密码的结构特征,构造一条4轮不可能差分路径,通过在不可能差分路径前面增加2轮、后面增加1轮的方式,对7轮ARIA密码算法进行不可能差分攻击.研究结果表明:7轮攻击共需要2119选择明文和大约2218次7轮加密运算.与已有结果相比较,该次攻击进一步降低了数据复杂度和时间复杂度.同时,在4轮不可能差分路径基础上,通过前面增加2轮、后面增加2轮的方式,首次提出了对ARIA密码算法的8轮不可能差分的新攻击.研究结果表明:8轮不可能差分攻击共需要2207选择明文和大约2346次8轮加密运算,已超过穷举搜索的攻击复杂度,故可认为在该路径下的8轮不可能差分攻击中ARIA密码算法是安全的.

分组密码TWINE的中间相遇攻击

将Biclique初始结构与标准的三子集中间相遇攻击相结合,给出了一种普遍的中间相遇攻击模式.与Biclique分析相比,该模式下的攻击作为算法抗中间相遇攻击的结果更为合理.进一步地,评估了算法TWINE抗中间相遇攻击的能力,通过合理选择中立比特位置以及部分匹配位置,给出了18轮TWINE-80以及22轮TWINE-128算法的中间相遇攻击结果.到目前为止,这是TWINE算法分析中数据复杂度最小的攻击结果.

LBlock算法的改进中间相遇攻击

LBlock算法是2011年在ACNS会议上提出的轻量级分组密码算法,目前已存在17轮、19轮LBlock算法的中间相遇攻击.文中评估LBlock算法在预建表中间相遇攻击下的安全性.预建表中间相遇攻击提出并发展于AES算法(高级加密标准)的安全性分析,是近些年密码分析中的一个研究热点.预建表中间相遇攻击属于典型的区分器类攻击,包含离线和在线两个阶段.文中通过综合离线阶段区分器的建立过程和在线阶段密钥的恢复过程,利用程序搜索LBlock算法有效区分器与对应初始密钥的最优攻击参数.结果表明,LBlock算法存在11轮区分器,21轮LBlock算法不抵抗预建表中间相遇攻击,攻击的数据复杂度仅为2^(34.1)选择明文,计算复杂度为2^(75.8)次21轮加密,存储复杂度为2^(74.8)个64比特块.与LBlock算法已有中间相遇攻击相比,文中将攻击轮数由19轮扩展至21轮,刷新了LBlock算法在中间相遇攻击下的安全性评估结果.与不可能差分、积分分析等其他分析结果相比,文中攻击具有显著的低数据复杂度,在实际攻击环境下具有重要意义.此外,为了提高LBlock密钥扩展算法的扩散速度,汪艳凤等人提出了一种新的密钥扩展算法.文中评估了采用新的密钥扩展算法的LBlock在预建表中间相遇攻击下的安全性,并成功得到了复杂度优于穷举搜索的20轮攻击,结果显示新的密钥扩展算法以1轮的优势增强了LBlock算法抵抗此类攻击的能力.

标题位置等因素对表图使用绩效的影响

考察表、图标题位置、数据复杂度和问题难度对表、图使用绩效的影响。49名大学生随机分为表格组和图形组。结果表明:(1)从表中提取信息更快、更准确,但对图中信息的回忆正确率更高;(2)标题位于上方时提取信息更快更准,回忆正确率也更高;(3)数据复杂度主要影响反应正确率;(4)对简单问题的反应既快又准,但回忆正确率较低。