论文研究 一种引入复杂网络理论的软件数据流脆弱点识别方法.pdf

研究了卫星LTE上行同步系统在单粒子效应影响下软件数据流错误的脆弱点识别问题，并针对现有错误传播分析方法对大容量数据处理软件脆弱点识别存在较大偏差的问题，结合星载LTE上行同步处理大容量数据处理需求，引入复杂网络理论，提出一种基于网络节点度的软件数据流脆弱点识别方法。该方法以错误传播分析方法为基础，通过定义单粒子翻转错误渗透率，采用矩阵化描述方法构建了错误传播网络模型，将软件数据流脆弱点挖掘问题转换为网络关键节点挖掘问题，以一定的虚警概率搜索所有的局部极值，从而实现该虚警概率下全部的数据流脆弱点挖掘。仿真结果表明，该方法可有效识别星载LTE上行同步处理大容量数据处理中的脆弱点。1102·计算机应用研究第32卷外的一些研究也从不同的方面证实了大规模软件具有复杂网a)SEU错误传递矩阵 MPEPS"的生成。按照系统模块络的特性。以复杂网络的视角研究软件特性为研究方向提出间的数据流交互关系,依次生成系统所有的错误传递矩阵,每了一种新的思路。对大量开源软件进行分,发现这些软件都个错误传递矩阵构成了系统错误传递网络的局部信息。具有小世界和无标度特性,对Java和linx等软件系统进行分 MPEPS-的生成方法只需要确定其模块间数SEU渗透率析也得到相同的结论。同时,复杂理论的无标度(即82原则)PE4。对于PEPS求解采用的方法为:依据SEU造成的特性表明大型软件系统的程序内部结构并不满足随机网络特借误改变信号数值,以信号改变前后信号k的偏差作为点而是存在无标度特性,即少量的节点往往拥有大量的连接,PEPs而大部分节点只有少数的连接,一般而言它们符合8-2原则。b)度矩阵MD的生成以及数据的加权遗择。对所有的错因此,软件缺陷经常在应用系统程序结构网络中呈现出亵集的特点,即应用系统80%的软件缺陷存在于20%的程序模块中误传递矩阵按行求和,得到所有元素的度,计算方法见式(4)因此若能合理地利用复杂网络理论,可以显著地提高脆弱点挖式(4)所表示的节点度是一种加权节点度,是对节点的度以信掘的效率。号SFU渗透率进行加权。)系统比特级脆弱点识别。统计不同数据位s上U渗透率3引入复杂网络理论的脆弱点识别并排序,数据位SU渗透率越高,其流入系统的可能性就越大,其脆弱性也越高。复杂网络是自然界和人类社会中普遍存在的一类复杂系d)系统模块级脆弱点识别。统计模块的平均节点度,即统,现实世界中的复杂网络无处不在。复杂网络的研究以数学对模坎的度矩阵求均值。模块的平均节点度越高,则模坎对系中的图论作为理论基础,大量应用统计物理学的方法和工具,对网络的几何性质、形成机制、演化规律、结构稳定性和动力学统的影响越大,是系统的关键坏节。等多个方面进行了大量的研究,也取得了丰硕的研究成果。复e)系统信号级脆弱点识别。基于节点度进行信号脆弱点杂网络可以用来描述从技术到生物直全社会各类开放复杂系识别是个通过节点的局部特性对节点进行筛选以寻找满足统的骨渠,而且是研究它们拓扑结构和动力学性质的有力全局要求的脆弱点因此需要合理地设计判决门限,取得漏检工具0。概率与虚警概率的均衡。当系统节点度符合无标度特性时以在复杂网络的研究中,有很多参数可以反映网络的特征8-2原则为标准,若需选岀数据错误对系统输出影晌最大的其中最重要的是节点的度分布、半均距离和集聚系数这三个参0%的数据,可将诜取系数k设为25%。同时考虑模块的平数。度参数被定义为该节点连接其他节点的数目。个节均错误渗透率可以表示模块对系统的影晌大小和模块的重要点的度分为入度和出度。节点的人度是指从其他节点指向该程度,因此对各个模块中对信号的筛选系数需要按照平均SEU节点的边的数量,节点的出度是指从该节点出发指向其他节点渗透率进行加权,计算公式如下边的数量。节点人度越大,表明该节点重用度越高;节点出度k×∑D1×(PP+D1∑D)2越大,表明该节点的复杂度越高。通常情况下,节点的度代表其中:D为模块i的数据总数,为模块i的平均SEU渗透率。节点在网络中的重要程度,度大节点在网络中的重要程度越高。与另外两个反映全局变量的参数相比,节点参数度与4卫星LTE数据流脆弱点识别度分布是一种反映网络局部性质的参数。基于错误传递矩阵结合节点参数度的定义可得到错误渗透率的数据节点的度矩4.1比特级脆弱点阵MD为卫星ITF上行同步系统中数据均以八位二进制数来表nD=∑ MPEPS+1(4)示。统计各模块SFU错误渗透率PP(Ⅰ)的平均值如表1式中:MD表示由第/个模块所有输入数据的度构成的矩阵所示。模块1的第k个数据的度即为度矩阵MD的第k个元素MD表1各模块不同数据位SEU错误渗透率(h)。∑ MPEPS1(,:)表示对惜误传递矩阵 MPEPS模块1模块2模块3模块4模块5按行求和。由于错误传递矩阵 MPEPS+的元素是数据间0.05350.05730.03040.02880.错误渗透率,因此式(4)所表示的度值,其实是一种加权的度PFP(2):20.05900.06320.093660.04800.1132值,权值为SU错误渗透率。0.1377为挖掘LTE上行同步系统的数据流脆弱点,本文将采用PE(3),0.06860.0735PE(4)4g0.08960.09250.08110.07530.1579最优化的分析方法,将其看做是一种寻找仝局最优问题,即邓PEP(0.0913085614300.12060.1979所有要考察的系统数据设共集合为D={D1,D2,…},以不同PEP(6A=的数据错误对系统的影响大小为评价标准,建立评价标准集合0.0%640.03130.18920.11490.2553ED={ED1,ED2,…},依据E(i)≥EA的准则(E为判决门限PE7).:0.09700.09590.22840.14180.321可依据实际情况定义,这里以8-2原则为标准,选出数据错误PFP(8):20.10530.09770.15420.16740.3916对系统输出影响最大的20%的数据),选出对应的信号。但是由表1可以看出,在整个卫星LTE上行同步系统中,发生由于一个实际的系统往往过于复杂,无法用简单的模型来描在高位的数据错误具有更高的错误渗透率囚为发生在数据高述,直接遍历寻找最优值的方法往往过十复杂而难以实现。因位的错误比发生在效据低位对原始数据的破坏更为严重,所以此这里将利用节点参数度这样一个反陝网络局部性质的变量,其错误渗透率也更高,同时也说明数据的高位相对于数据的低将遍历仝局的搜索改为通过对局部极值点即对数据度值的挖位对SEU的错误更敏感而且具有明显的差别,因此在装配容掘与验算来进行脆弱点挖掘。具体做法如下错机制时数据的高低位需釆用不同的数据防护措施第4期卫彦伉,等:一种引入复杂网络理论的软件教据流脆弱占识别方法11034.2模块级脆弱点识别符合复杂网络中无标度的特性,即少数的信号具有较高的度为验证本文所提脆弱点挖掘方法的有效性,现将本文所提值,并近似符合82定律。同时,由于引入复杂网络的脆弱点方法与基于软件仿真故障注入方法的结果进行比对。故障注识别方法听选用的评价指标一节点度是一个反块网络局部入方法认别LE上行同步处理模块级脆弱点的具体做法是:信息的变量,因此其故障注入方法相比出于多个局部极值点的首先编写故障注入函数Su6mmc()实现对信号注入SHU出现而存在一定的误差,但是以节点度为基础的脆弱点识别方错误的功能;然后将系统运行的各阶段数据保存为数据文件法仍然能够将信号级脆弱性以节点度的形式成功反映出来,即并利用Su6mmc()对数据进行故障汁入,接着重新装载故故障注入方式识别处理的信号级脆弱点在复杂网络方法中也障注入后数据并运行系统;最后统计系统同步性能(以同步接具有较高的节点度值。为此对于引入复杂N络理论的脆弱点收的峰均功率比为标准)与未发生SEU错误时系统同步性能识别方法,可以作为一种快速高效的脆点识别方法。的偏差。故障注入方法对任一数据的故障注入都需要进行多5结束语次实验并统计结果才能实现,其实现难度大、周期长对于模块级的系统脆弱点识别,木文所提方法为:统计各本文在定义信号SEU错误渗透率的基础上,以错误传播个模块信号的平均节点度并排序,平均节点度越高,则该模块分析为基础,枃建错误传播网络,并引λ复杂网络理论,将寻求脆弱性乜越高。故障注人方法为统计各饣模墺信亐的平均影玊星Ⅰˆ上行冋步算法的数据流脆弱点转换为寻找最优值问响偏差。两者识别结果对照如图2所示。题,通过首先筛选并验算极值点,得到全局最优值,以挖掘凵整图2所示的两种方法在识别系统模块级脆弱点的结果相个系统的脆弱点,可进一步为系统装配容锖机制提供依据。吻合。同时图2表明星载LTE上行同步处理对系统输入模块参考文献的依赖性较低,对靠近输出端的模块依赖性较高。另外,由于[1 UMAN(. n-indluced soft errors in advanced semi- on模块4是整个数据流的·个明显收缩的模块(由I28个信号生duetor technologies [J. IEEE Trans on Device and Materials Re成62个信号),导致模块4的信号普遍具有较高的节点度值liablity,2005,5(3):305-316.并且经过IFFT运算后,对部分数据错误具有放大的作用,导致[2贺朝会.单粒子效应研究的现状和动态[冂.抗核加固,200017模块4对系统的影响最大4.3信号级脆弱点识别[3』徐建军,谭庆平,熊磊,等.一种针对软错误的裎序可靠性定量分析方法[J].电子学报,2011,39(3):675-679在对系统进行系统信号级脆弱点识别时,也将引入复杂网14」 LI Xiao-don, ADVE S V, BOSE P,etal. Softech: an architec络识别方法与模拟故障注入识别方法进行对比。两种方法对ture-level tool for modeling and analyzing soft errors[ C]// Proe of In各个模块的信号脆弱点识别结果如图3~7所示。ternational Conference on Dependable Systems and Networks. [S子平打度阳核牲监丙到IEEE Press,2005:496-505创015[5 MUKHERJEE SS, WEAVER C, EMER J, ct al. A systematic me0.05thodology to compute the architectural vulnerability factors for a high0100120140模块的信号字performance microprocessor[ C]//Proc of the 36th Annual IEEE06[了债拟黑上入办六性只到0.0头章主△的努明白认为ACM International Symposium on Microarchitecture. [SL.]: IEEEPress,2003:29-40204060B010012014[6 HILLER M, JHUMKA A, SURI N. EPIC: profiling the propagation模块的信号序列图2模块级识别结果对比图3模块1信号脆弱的识别and effect of data enors in softwaeLJ. IEEE Trans on Computers结果对比2004,53(5):512-530当十节点度明学爽利转0.[冂]李爱国,洪炳镕,王司.基于错误传播分析的软件脆弱点识别方法研究[J].计算机学报,2007,30(11):1910-1921[8 3GPP 'lS 36. 211(v2. 1. U), Evolved universal terrestrial radio access模块2的信号序列模块3的管号序列(E-UTRA); Physical channels and modulation release 9)[SI■或障生∧肉消号究识烁論00lLL-IPF[9 MANOLAKIS K, ESTEVEZ D,JUNGICKEL V, et al. A closed con-14020406080100120140模块2的信号序列cept for synchronization and cell search in 3GPP LTE systems[C]//图4模块2信号脆弱的识别图5模块3信号脆弱的识别Proc of ieee Wireless Communications and Networking Conference结果对比结果对比2009:1-6[1U]孙世温,夏承遗,王莉.基于复杂网络竹软件结构度量方法综述102030405050701,J.智能系统学报,201,6(3):208-212]韩明畅,李德毅,刘常昱.软件屮的网络化特征及其对软件质量的模坎4信号序列奖块的信号序列57改摩壮人的省号晃列成我别贡献[冂.计算机工程与应用,2006,42(20):29-31[12]刘婧.基于复杂网络的软件结构分析及优化研究[D].武汉:武汉大学,2007块4的信专序列[13]吴金闪,狄増如.从统计物理学看复杂网络硏究[J].物理学进图6模块4信号脆弱的识别图7樸块5信号脆弱的识别展,2004,24(1):18-46结果对比结果对比[4]夏启明.软伫测试及评价的复用策略硏究及其实现[D].武汉:武由以上可知星载L悝上行同步处理的错误传播网络确实汉大学,2010